This notebook is written with reticulate, a package that allows inter-operation between R and Python.


1 Motivation

Why do we need to explain a machine learning model? The benefit of an explanable model against a black-box model is for the model to be trusted. Trust can be important in many real applications where the successful deployment of a machine learning model requires the trust from end users. Sometimes trust plays a even bigger role than model accuracy.

Other than trust, model explainability (or interpretability, interchangeably used hereafter) may also guide us in the correct direction to further improve the model.1

In general, linear model is more interpretable than non-linear model. But the former also suffers from lower accuracy. More advanced and hence complicated model usually has worse interpretability.

One should not confuse model explainability with the actual causality. Being able to explain a model doesn’t mean that we can identify any ground-truth causal relation behind the model. Model explainability is for and only for the model, but not for the facts we’d like to model. Nevertheless, understand how we can reason the model definitely will help us better model the actual pattern behind the scence.

In this notebook we will walk through 3 popular approaches of model prediction explanation, each of them comes with a dedicated Python package:

  1. shap
  2. lime
  3. interpret

2 Explanation Models

An explanation model \(g(x)\) is an interpretable approximation of the original model \(f(x)\). Its sole purpose is to give extra explainability the original model fails to provide, due to its own complexity.

The general idea is to use a simplified input \(x\prime\) such that \(x = h_x(x\prime)\), where \(h_x(\cdot)\) is a mapping function for any given raw input \(x\). Then the interpretable approximation can be written as:

\[ g(x\prime) \approx f(h_x(x\prime)). \]

The additive feature attribution methods specify the explanation model of the following form:

\[ g(x\prime) = \phi_0 + \sum_{i = 1}^m \phi_i x_i\prime, \]

where \(m\) is total number of simplified features, \(x\prime \in \{0, 1\}\) simply an indicator.2 Apparently, the choice of an additive model is for (linear) intrepretability. The simplified features are an interpretable representation of the original model features.

3 LIME

One very popular such above additive model is LIME (Ribeiro, Singh, and Guestrin (2016)). LIME stands for Local Interpretable Model-Agnostic Explanations. As its full name suggests, LIME can be applied to any machine learning model. LIME achieves prediction-level interpretability by approxmiating the original model with an explanation model locally around that prediction.

TODO: Add theory briefing here.

3.1 On Text Classifiers

For text classification problem, the most straightforward interpretable representation of the model features will be a binary indicator vector of bag of words. So the explanation model will try to reason which word or token is driving the prediction in what direction. And this is true no matter the form of the original model feature. May it be a word count matrix, a term frequency-inverse document frequency (TF-IDF) matrix, or numerical embeddings.

In the following we will use Large Movie Review Dataset to do a binary sentiment classification exercise. We will use machine learning libraries such as scikit-learn and tensorflow to quickly build models and use lime to experiment explanation modeling.

import os
import logging
logging.getLogger("tensorflow").setLevel(logging.ERROR)
import warnings
warnings.simplefilter(action="ignore", category=UserWarning)
warnings.simplefilter(action="ignore", category=FutureWarning)

import matplotlib.pyplot as plt
import numpy as np
import pandas as pd

import tensorflow as tf
print(tf.__version__)
2.0.0
if tf.test.is_gpu_available():
  print(tf.test.gpu_device_name())
/device:GPU:0
import sklearn
from sklearn.feature_extraction.text import TfidfVectorizer
from sklearn.ensemble import RandomForestClassifier
from sklearn.pipeline import make_pipeline
from sklearn.metrics import classification_report, roc_auc_score
from sklearn.model_selection import train_test_split
import joblib

print(sklearn.__version__)
0.22
# Create model dir to cache all models trained in the notebook.
model_dir = "models"
if not os.path.exists(model_dir):
    os.makedirs(model_dir)

# Directory to cache dataset.
home = os.path.expanduser("~")
cache_dir = os.path.join(home, ".keras")

First, we prepare the movie review dataset.3

import tensorflow_datasets as tfds

# Load the data as tf.data.Dataset.
imdb = tfds.load(name="imdb_reviews", as_supervised=True,
                 data_dir=os.path.join(home, "tensorflow_datasets"))

The dataset is a perfectly balanced dataset with 50,000 examples, half for positive and half for negative sentiment.

# Extract all texts as list since we want to use libraries other than tensorflow as well.
# And since this is a small dataset, we don't care about memory usage.
# We skip the use of a dataset iterator.
imdb_reviews_train = []
imdb_reviews_test = []
imdb_y_train = []
imdb_y_test = []
for x, y in imdb["train"].batch(128):
  imdb_reviews_train.extend(x.numpy())
  imdb_y_train.extend(y.numpy())
for x, y in imdb["test"].batch(128):
  imdb_reviews_test.extend(x.numpy())
  imdb_y_test.extend(y.numpy())

# TF works on bytes, but some other packages may only work on decoded string.
imdb_reviews_train = [b.decode("utf8") for b in imdb_reviews_train]
imdb_reviews_test = [b.decode("utf8") for b in imdb_reviews_test]
imdb_y_train = np.array(imdb_y_train)
imdb_y_test = np.array(imdb_y_test)

# Take one review.
print(imdb_reviews_train[87])
Any movie that portrays the hard-working responsible husband as the person who has to change because of bored, cheating wife is an obvious result of 8 years of the Clinton era.<br /><br />It's little wonder that this movie was written by a woman.
print(imdb_y_train[87])  # Label. 0 as negative and 1 as positive.
0

We use the data prepared by tensorflow-datasets here just to save some time. For those who want to process the data in its very original format (where one review is in one .txt file), the files can be downloaded by this piece of code:

imdb_remote_path = "https://ai.stanford.edu/~amaas/data/sentiment/aclImdb_v1.tar.gz"
imdb_fname = os.path.basename(imdb_remote_path)
imdb_local_path = os.path.join(cache_dir, "datasets", imdb_fname)

if not os.path.exists(imdb_local_path):
  _ = tf.keras.utils.get_file(fname=imdb_fname, origin=imdb_remote_path,
                              extract=True, cache_dir=cache_dir)

3.1.1 Explain Random Forest

Let’s build a random forest with TF-IDF as our feature space. We will use the popular scikit-learn library for implementation.4

# We drop words that are too frequent or too rare in the training dataset.
imdb_vectorizer = TfidfVectorizer(lowercase=True, min_df=10, max_df=.9)
imdb_X_train = imdb_vectorizer.fit_transform(imdb_reviews_train)
imdb_X_test = imdb_vectorizer.transform(imdb_reviews_test)
print(len(imdb_vectorizer.vocabulary_))  # Without OOV token.
18518
imdb_rf_model_file = "models/text_rf.joblib"

# Save/reload the model to save notebook rendering time.
if os.path.exists(imdb_rf_model_file):
  imdb_rf = joblib.load(imdb_rf_model_file)
else:
  imdb_rf = RandomForestClassifier(n_estimators=300, random_state=64, n_jobs=-2)
  _ = imdb_rf.fit(imdb_X_train, imdb_y_train)
  _ = joblib.dump(imdb_rf, imdb_rf_model_file)

imdb_rf_pred = imdb_rf.predict(imdb_X_test)
imdb_rf_yhat = imdb_rf.predict_proba(imdb_X_test)[:,1]

print(classification_report(imdb_y_test, imdb_rf_pred))
              precision    recall  f1-score   support

           0       0.84      0.86      0.85     12500
           1       0.86      0.84      0.85     12500

    accuracy                           0.85     25000
   macro avg       0.85      0.85      0.85     25000
weighted avg       0.85      0.85      0.85     25000
print(roc_auc_score(imdb_y_test, imdb_rf_yhat))
0.9274221727999999

As a baseline without extensive tuning (we didn’t tune anything indeed!), random forest seems to perform fairly well on this dataset.

As part of the algorithm’s design we are able to derive a global view of feature importance. This is based on how much each feature can reduce the impurity during all tree splittings. For example, we can plot the top 20 features:

sorted_vocab = sorted(imdb_vectorizer.vocabulary_.items(), key=lambda kv: kv[1])
sorted_vocab = [w for w, i in sorted_vocab]

imdb_rf_feat_imp = pd.Series(imdb_rf.feature_importances_, index=sorted_vocab).sort_values()
ax = imdb_rf_feat_imp.tail(20).plot(kind="barh")
plt.show()

Interpretation of the impurity-based ranking must be very careful though. For example, related features will theoretically have similar impact but only one of it will gain higher score (and suppress the other) in the ranking. Which one stands out is totally random.

In general it is NOT recommended to use impurity or even loss-based feature ranking to interpret a tree ensemble model. Such ranking information is still useful to understand different aspects of the model, and can be used to subset feature to counter over-fitting issue, if any. But it won’t help really explain the model per se. And this is exactly why we need a explanation model in the first place.

Now move on to model explanation with LIME:

from lime.lime_text import LimeTextExplainer

# We need a pipeline since LimeTextExplainer.explain_instance expects raw text input.
imdb_rf_pipe = make_pipeline(imdb_vectorizer, imdb_rf)
imdb_rf_explainer = LimeTextExplainer(class_names=["Negative", "Positive"])

imdb_rf_tp_idx = np.where(np.logical_and(imdb_rf_pred == 1, imdb_y_test == 1))[0]
imdb_rf_fp_idx = np.where(np.logical_and(imdb_rf_pred == 1, imdb_y_test == 0))[0]

# We take one true positive and one false positive example to demo explanation.
imdb_rf_tp_exp = imdb_rf_explainer.explain_instance(
  imdb_reviews_test[imdb_rf_tp_idx[0]], imdb_rf_pipe.predict_proba, num_features=6)
imdb_rf_fp_exp = imdb_rf_explainer.explain_instance(
  imdb_reviews_test[imdb_rf_fp_idx[0]], imdb_rf_pipe.predict_proba, num_features=6)
# For ipynb, one can simply call imdb_tp_exp.show_in_notebook(text=True) to embed the html output.

imdb_rf_tp_exp.save_to_file("/tmp/explain_text_rf_tp.html")
imdb_rf_fp_exp.save_to_file("/tmp/explain_text_rf_fp.html")

A True Positive Prediction Explained

A False Positive Prediction Explained

TODO: Discuss the result.

3.1.2 Explain Neural Nets with Word Embeddings

Now let’s try a neural network model with word embeddings trained from scratch. We use tensorflow.keras API to quickly build and train a neural net. We average word embeddings as the document embeddings for each review, then feed-forward a ReLU layer before the sigmoid activation for cross-entropy optimization.

As an exercise, instead of re-using the vocabulary built by TfidfVectorizer with scikit-learn, we will re-tokenize the text data with keras.preprocessing module. The inherent consistency under the Keras framework will also simplify our latter works on network layering.

from tensorflow.keras.preprocessing.text import Tokenizer
from tensorflow.keras.preprocessing.sequence import pad_sequences

# Build vocabulary. We use similar size as in our previous TfidfVectorizer.
# Since we will use zero padding, 0 cannot be used as OOV index.
# Keras tokenizer by default reserves 0 already. OOV token, if used, will be indexed at 1.
# Note that len(tokenizer.index_word) will be all vocabulary instead of `num_words`.
vocab_size = 20001  # +1 for 0 index used for padding.
oov_token = "<unk>"
tokenizer = Tokenizer(lower=True, oov_token=oov_token, num_words=vocab_size)
tokenizer.fit_on_texts(imdb_reviews_train)

# Encode text with padding to ensure fixed-length input.
seq_train = tokenizer.texts_to_sequences(imdb_reviews_train)
seq_train_padded = pad_sequences(seq_train, padding="post")
maxlen = seq_train_padded.shape[1]
seq_test = tokenizer.texts_to_sequences(imdb_reviews_test)
seq_test_padded = pad_sequences(seq_test, padding="post", maxlen=maxlen)

assert tokenizer.index_word[1] == oov_token
assert seq_train_padded.max() == vocab_size - 1

# Wrap Keras Sequential model with scikit-learn API.
# This is because LimeTextExplainer seems buggy with a native Keras model.
nn_model_file = "models/text_clf_nn.h5"

def nn_model_fn():
  embedding_size = 64
  model = tf.keras.Sequential([
    tf.keras.layers.Embedding(
      vocab_size, embedding_size, input_length=maxlen,
      mask_zero=True, name="word_embedding"),
    tf.keras.layers.GlobalAveragePooling1D(name="doc_embedding"),
    tf.keras.layers.Dense(embedding_size / 2, activation="relu", name="relu"),
    tf.keras.layers.Dense(1, activation="sigmoid", name="sigmoid")
  ], name="nn_classifier")
  model.compile(optimizer="adam",
                loss="binary_crossentropy",
                metrics=["accuracy"])
  return model

print(nn_model_fn().summary(line_length=90))
Model: "nn_classifier"
__________________________________________________________________________________________
Layer (type)                            Output Shape                        Param #       
==========================================================================================
word_embedding (Embedding)              (None, 2493, 64)                    1280064       
__________________________________________________________________________________________
doc_embedding (GlobalAveragePooling1D)  (None, 64)                          0             
__________________________________________________________________________________________
relu (Dense)                            (None, 32)                          2080          
__________________________________________________________________________________________
sigmoid (Dense)                         (None, 1)                           33            
==========================================================================================
Total params: 1,282,177
Trainable params: 1,282,177
Non-trainable params: 0
__________________________________________________________________________________________
None
imdb_nn = tf.keras.wrappers.scikit_learn.KerasClassifier(nn_model_fn)
if os.path.exists(nn_model_file):
  # Restore the model with wrapper.
  imdb_nn.model = tf.keras.models.load_model(nn_model_file)
  imdb_nn.classes_ = np.array([0, 1])
else:
  metrics = imdb_nn.fit(
    x=seq_train_padded, y=imdb_y_train,
    batch_size=256, epochs=10,
    validation_data=(seq_test_padded, imdb_y_test),
    validation_steps=20,
    callbacks=[
      tf.keras.callbacks.EarlyStopping(monitor="val_loss", patience=2),
      tf.keras.callbacks.ModelCheckpoint(nn_model_file, monitor="val_loss", save_best_only=True)
    ],
    verbose=2)

imdb_nn_yhat = np.squeeze(imdb_nn.predict(seq_test_padded))
imdb_nn_pred = (imdb_nn_yhat > .5).astype(int)

print(classification_report(imdb_y_test, imdb_nn_pred))
              precision    recall  f1-score   support

           0       0.88      0.89      0.89     12500
           1       0.89      0.88      0.89     12500

    accuracy                           0.89     25000
   macro avg       0.89      0.89      0.89     25000
weighted avg       0.89      0.89      0.89     25000
print(roc_auc_score(imdb_y_test, imdb_nn_pred))
0.88776
def nn_predict_fn(text):
  # This is for sklearn wrapper only.
  seq = tokenizer.texts_to_sequences(text)
  seq = pad_sequences(seq, padding="post", maxlen=maxlen)
  return imdb_nn.predict_proba(seq)

imdb_nn_explainer = LimeTextExplainer(class_names=["Negative", "Positive"])

# Explain the same examples as in RF.
imdb_nn_tp_exp = imdb_nn_explainer.explain_instance(
  imdb_reviews_test[imdb_rf_tp_idx[0]], nn_predict_fn, num_features=6)
imdb_nn_fp_exp = imdb_nn_explainer.explain_instance(
  imdb_reviews_test[imdb_rf_fp_idx[0]], nn_predict_fn, num_features=6)

imdb_nn_tp_exp.save_to_file("/tmp/explain_text_nn_tp.html")
imdb_nn_fp_exp.save_to_file("/tmp/explain_text_nn_fp.html")

TODO: Discuss the difference between RF and NN.

3.1.3 Explain Transfer Learning

One step further, let’s use pre-trained word embeddings for the neural nets and build another explanation model. We will use GloVe (Pennington, Socher, and Manning (2014)). We use just the smaller GloVe model since our dataset is quite small. In building the GloVe embeddings we need to take special care about out-of-vocabulary token AND padding index since we will be using the Keras API.

# Download GloVe pre-trained embeddings.
# The file is about 800MB so may take some time.
home = os.path.expanduser("~")
cache_dir = os.path.join(home, ".keras")
glove6b_remote_path = "http://nlp.stanford.edu/data/glove.6B.zip"
glove6b_local_path = os.path.join(cache_dir, "datasets", "glove.6B.50d.txt")
glove6b_fname = os.path.basename(glove6b_remote_path)
if not os.path.exists(glove6b_local_path):
  _ = tf.keras.utils.get_file(fname=glove6b_fname, origin=glove6b_remote_path,
                              extract=True, cache_dir=cache_dir)

glove_all = pd.read_csv(glove6b_local_path, sep=" ", header=None, index_col=0, quoting=3)
# Map vocabulary to pre-trained embeddings.
matched_toks = []
for i, w in tokenizer.index_word.items():
  if i < vocab_size:
    if w in glove_all.index:
      matched_toks.append(w)
    else:
      matched_toks.append(oov_token)

# Note that GloVe pre-trained embeddings does not include its own OOV token.
# We will use a global average embedding to represent OOV token.
print(len([t for t in matched_toks if t == oov_token]))  # How many OOVs?
861
glove_all.loc[oov_token] = glove_all.values.mean(axis=0)
glove = glove_all.loc[matched_toks].values

# Append dummy 0-index vector to support padding.
glove = np.vstack([np.zeros((1, glove.shape[1])), glove])
print(glove.shape)
(20001, 50)

Now let’s build the neural network. Most of the code will be the same as before, only the Embedding layer now we will use a constant matrix for initialization. We make the GloVe embeddings trainable so it will further adapt to our specific dataset.

tr_model_file = "models/text_clf_tr.h5"

def tr_model_fn():
  embedding_size = glove.shape[1]
  model = tf.keras.Sequential([
    tf.keras.layers.Embedding(
      vocab_size, embedding_size, input_length=maxlen,
      embeddings_initializer=tf.keras.initializers.Constant(glove),
      trainable=True, mask_zero=True, name="glove_embedding"),
    tf.keras.layers.GlobalAveragePooling1D(name="doc_embedding"),
    tf.keras.layers.Dense(embedding_size / 2, activation="relu", name="relu"),
    tf.keras.layers.Dense(1, activation="sigmoid", name="sigmoid")
  ], name="tr_classifier")
  model.compile(optimizer="adam",
                loss="binary_crossentropy",
                metrics=["accuracy"])
  return model

print(tr_model_fn().summary(line_length=90))
Model: "tr_classifier"
__________________________________________________________________________________________
Layer (type)                            Output Shape                        Param #       
==========================================================================================
glove_embedding (Embedding)             (None, 2493, 50)                    1000050       
__________________________________________________________________________________________
doc_embedding (GlobalAveragePooling1D)  (None, 50)                          0             
__________________________________________________________________________________________
relu (Dense)                            (None, 25)                          1275          
__________________________________________________________________________________________
sigmoid (Dense)                         (None, 1)                           26            
==========================================================================================
Total params: 1,001,351
Trainable params: 1,001,351
Non-trainable params: 0
__________________________________________________________________________________________
None
imdb_tr = tf.keras.wrappers.scikit_learn.KerasClassifier(tr_model_fn)
if os.path.exists(tr_model_file):
  # Restore the model with wrapper.
  imdb_tr.model = tf.keras.models.load_model(tr_model_file)
  imdb_tr.classes_ = np.array([0, 1])
else:
  imdb_tr = tf.keras.wrappers.scikit_learn.KerasClassifier(tr_model_fn)
  metrics = imdb_tr.fit(
    x=seq_train_padded, y=imdb_y_train,
    batch_size=256, epochs=20,
    validation_data=(seq_test_padded, imdb_y_test),
    validation_steps=20,
    callbacks=[
      tf.keras.callbacks.EarlyStopping(monitor="val_loss", patience=2),
      tf.keras.callbacks.ModelCheckpoint(tr_model_file, monitor="val_loss", save_best_only=True)
    ],
    verbose=2)

imdb_tr_yhat = np.squeeze(imdb_tr.predict(seq_test_padded))
imdb_tr_pred = (imdb_tr_yhat > .5).astype(int)

print(classification_report(imdb_y_test, imdb_tr_pred))
              precision    recall  f1-score   support

           0       0.88      0.90      0.89     12500
           1       0.89      0.87      0.88     12500

    accuracy                           0.89     25000
   macro avg       0.89      0.89      0.89     25000
weighted avg       0.89      0.89      0.89     25000
print(roc_auc_score(imdb_y_test, imdb_tr_yhat))
0.8855200000000001
def tr_predict_fn(text):
  # This is for sklearn wrapper only.
  seq = tokenizer.texts_to_sequences(text)
  seq = pad_sequences(seq, padding="post", maxlen=maxlen)
  return imdb_tr.predict_proba(seq)

imdb_tr_explainer = LimeTextExplainer(class_names=["Negative", "Positive"])

# Explain the same examples as in RF.
imdb_tr_tp_exp = imdb_tr_explainer.explain_instance(
  imdb_reviews_test[imdb_rf_tp_idx[0]], tr_predict_fn, num_features=6)
imdb_tr_fp_exp = imdb_tr_explainer.explain_instance(
  imdb_reviews_test[imdb_rf_fp_idx[0]], tr_predict_fn, num_features=6)

imdb_tr_tp_exp.save_to_file("/tmp/explain_text_tr_tp.html")
imdb_tr_fp_exp.save_to_file("/tmp/explain_text_tr_fp.html")

TODO: Discussion.

3.1.4 Explain Recurrent Neural Nets

As a final exercise on text classification, let’s experiment the explanation model with a recurrent neural network (RNN). Note that, even for a single layer, this will be prohibitively slow without a GPU.

rnn_model_file = "models/text_clf_rnn.h5"

def rnn_model_fn():
  embedding_size = 64
  model = tf.keras.Sequential([
    tf.keras.layers.Embedding(
      vocab_size, embedding_size,
      input_length=maxlen, mask_zero=True, name="word_embedding"),
    tf.keras.layers.GRU(64, dropout=.2, name="GRU"),
    tf.keras.layers.Dense(1, activation="sigmoid", name="sigmoid")
  ], name="rnn_classifier")
  model.compile(optimizer="adam",
                loss="binary_crossentropy",
                metrics=["accuracy"])
  return model

print(rnn_model_fn().summary(line_length=90))
Model: "rnn_classifier"
__________________________________________________________________________________________
Layer (type)                            Output Shape                        Param #       
==========================================================================================
word_embedding (Embedding)              (None, 2493, 64)                    1280064       
__________________________________________________________________________________________
GRU (GRU)                               (None, 64)                          24960         
__________________________________________________________________________________________
sigmoid (Dense)                         (None, 1)                           65            
==========================================================================================
Total params: 1,305,089
Trainable params: 1,305,089
Non-trainable params: 0
__________________________________________________________________________________________
None
imdb_rnn = tf.keras.wrappers.scikit_learn.KerasClassifier(rnn_model_fn)
if os.path.exists(rnn_model_file):
  #  # Restore the model with wrapper.
  imdb_rnn.model = tf.keras.models.load_model(rnn_model_file)
  imdb_rnn.classes_ = np.array([0, 1])
else:
  metrics = imdb_rnn.fit(
    x=seq_train_padded, y=imdb_y_train,
    batch_size=32, epochs=10,
    validation_data=(seq_test_padded, imdb_y_test),
    validation_steps=20,
    callbacks=[
      tf.keras.callbacks.EarlyStopping(monitor="val_loss", patience=2),
      tf.keras.callbacks.ModelCheckpoint(rnn_model_file, monitor="val_loss", save_best_only=True)
    ],
    verbose=2)

imdb_rnn_yhat = np.squeeze(imdb_rnn.predict(seq_test_padded))
imdb_rnn_pred = (imdb_rnn_yhat > .5).astype(int)

print(classification_report(imdb_y_test, imdb_rnn_pred))
              precision    recall  f1-score   support

           0       0.85      0.91      0.88     12500
           1       0.90      0.84      0.87     12500

    accuracy                           0.87     25000
   macro avg       0.88      0.87      0.87     25000
weighted avg       0.88      0.87      0.87     25000
print(roc_auc_score(imdb_y_test, imdb_rnn_yhat))
0.8733200000000001

Since the dataset is rather small, we didn’t see any advantage of RNN over a simple pooling embedding model. That’s see how the explanation can differ, again, for the same two examples:

def rnn_predict_fn(text):
  # This is for sklearn wrapper only.
  seq = tokenizer.texts_to_sequences(text)
  seq = pad_sequences(seq, padding="post", maxlen=maxlen)
  return imdb_rnn.predict_proba(seq)

imdb_rnn_explainer = LimeTextExplainer(class_names=["Negative", "Positive"])

# Explain the same examples as in RF.
imdb_rnn_tp_exp = imdb_rnn_explainer.explain_instance(
  imdb_reviews_test[imdb_rf_tp_idx[0]], rnn_predict_fn, num_features=6)
imdb_rnn_fp_exp = imdb_rnn_explainer.explain_instance(
  imdb_reviews_test[imdb_rf_fp_idx[0]], rnn_predict_fn, num_features=6)

imdb_rnn_tp_exp.save_to_file("/tmp/explain_text_rnn_tp.html")
imdb_rnn_fp_exp.save_to_file("/tmp/explain_text_rnn_fp.html")

TODO: Summarize all text models.

3.2 On Tabular Data Classifier

Lots of data can be represented in tabular format. Here we will use UCI Heart Disease dataset for demo. Particularly, we use the Cleveland dataset which is commonly used in machine learning research.5

ucihd_remote_path = "https://archive.ics.uci.edu/ml/machine-learning-databases/heart-disease/processed.cleveland.data"
ucihd_fname = os.path.basename(ucihd_remote_path)
ucihd_local_path = os.path.join(cache_dir, "datasets", ucihd_fname)

if not os.path.exists(ucihd_local_path):
  _ = tf.keras.utils.get_file(fname=ucihd_fname, origin=ucihd_remote_path,
                              extract=False, cache_dir=cache_dir)
ucihd_attr = [
  "age",
  "sex",
  "cp",  # chest pain type 1: typical angina 2: atypical angina 3: non-anginal pain 4: asymptomatic
  "trestbps",  # resting blood pressure (in mm Hg on admission to the hospital)
  "chol",  # serum cholestoral in mg/dl
  "fbs",  # (fasting blood sugar > 120 mg/dl) (1 = true; 0 = false)
  "restecg",  # resting electrocardiographic results 0: normal 1: having ST-T wave abnormality 2: showing probable or definite left ventricular hypertrophy by Estes' criteria
  "thalach",  # maximum heart rate achieved
  "exang",  # exercise induced angina (1 = yes; 0 = no)
  "oldpeak",  # ST depression induced by exercise relative to rest
  "slope",  #  the slope of the peak exercise ST segment
  "ca",  # number of major vessels (0-3) colored by flourosopy
  "thal",  # 3 = normal; 6 = fixed defect; 7 = reversable defect
  "label"  # diagnosis of heart disease (angiographic disease status) 0: < 50% diameter narrowing 1-4: > 50% diameter narrowing
]
ucihd = pd.read_csv(ucihd_local_path, header=None, names=ucihd_attr, na_values="?")
categorical_attr = ["cp", "fbs", "restecg", "exang", "thal"]
for col in categorical_attr:
  ucihd[col] = ucihd[col].astype("category")

# Clean label.
ucihd.loc[ucihd["label"] > 1, "label"] = 1

print(ucihd.shape)
(303, 14)
print(ucihd.groupby("label").size())  # Label distribution.
label
0    164
1    139
dtype: int64
print(ucihd.head())
    age  sex   cp  trestbps   chol  fbs restecg  thalach exang  oldpeak  slope   ca thal  label
0  63.0  1.0  1.0     145.0  233.0  1.0     2.0    150.0   0.0      2.3    3.0  0.0  6.0      0
1  67.0  1.0  4.0     160.0  286.0  0.0     2.0    108.0   1.0      1.5    2.0  3.0  3.0      1
2  67.0  1.0  4.0     120.0  229.0  0.0     2.0    129.0   1.0      2.6    2.0  2.0  7.0      1
3  37.0  1.0  3.0     130.0  250.0  0.0     0.0    187.0   0.0      3.5    3.0  0.0  3.0      0
4  41.0  0.0  2.0     130.0  204.0  0.0     2.0    172.0   0.0      1.4    1.0  0.0  3.0      0

The dataset contains both numerical and categorical features (all encoded in numerics already).

3.2.1 Explain Random Forest

# RF doesn't allow missing value.
# For categorical (as string) we can leave one special category for missing,
# but for numerical we need to do some special encoding or imputation.
ucihd_2 = ucihd.copy()
ucihd_2.loc[ucihd_2["ca"].isna(), "ca"] = -1  # Encode missing numerical.

# One-hot encode all categorical features.
ucihd_2 = pd.get_dummies(ucihd_2, columns=categorical_attr, dummy_na=True)
ucihd_y = ucihd_2.pop("label")
ucihd_X_train, ucihd_X_test, ucihd_y_train, ucihd_y_test = train_test_split(
  ucihd_2, ucihd_y.values, test_size=.3, random_state=64)

ucihd_rf = RandomForestClassifier(n_estimators=100, random_state=64)
_ = ucihd_rf.fit(ucihd_X_train, ucihd_y_train)

ucihd_rf_yhat = ucihd_rf.predict_proba(ucihd_X_test)[:,1]
ucihd_rf_pred = ucihd_rf.predict(ucihd_X_test)

print(classification_report(ucihd_y_test, ucihd_rf_pred))
              precision    recall  f1-score   support

           0       0.84      0.86      0.85        50
           1       0.82      0.80      0.81        41

    accuracy                           0.84        91
   macro avg       0.83      0.83      0.83        91
weighted avg       0.83      0.84      0.83        91
print(roc_auc_score(ucihd_y_test, ucihd_rf_yhat))
0.905609756097561

As one can see RF performs very well on this dataset.

To explain a model trained with numerical features, lime by default will discretize continous variables into quantiles for ease of interpretation. Discretization is done using statistics derived from the training dataset.

from lime.lime_tabular import LimeTabularExplainer

cat_ind = [i for i, col in enumerate(ucihd_2.columns) if "_" in col]
ucihd_rf_explainer = LimeTabularExplainer(
  ucihd_X_train.values, class_names=["Negative", "Positive"],
  feature_names=ucihd_2.columns,
  categorical_features=cat_ind)

ucihd_rf_tp_idx = np.where(np.logical_and(ucihd_rf_pred == 1, ucihd_y_test == 1))[0]
ucihd_rf_fp_idx = np.where(np.logical_and(ucihd_rf_pred == 1, ucihd_y_test == 0))[0]

# We take one true positive and one false positive for examples.
ucihd_rf_tp_exp = ucihd_rf_explainer.explain_instance(
  ucihd_X_test.iloc[ucihd_rf_tp_idx[0]], ucihd_rf.predict_proba, num_features=4)
ucihd_rf_fp_exp = ucihd_rf_explainer.explain_instance(
  ucihd_X_test.iloc[ucihd_rf_fp_idx[0]], ucihd_rf.predict_proba, num_features=4)

ucihd_rf_tp_exp.save_to_file("/tmp/explain_tab_rf_tp.html")
ucihd_rf_fp_exp.save_to_file("/tmp/explain_tab_rf_fp.html")

A True Positive Prediction Explained

A False Positive Prediction Explained

Discuss the two explanations.

3.2.2 Explain Gradient Boosting Trees

Gradient boosting trees (GBT) is a powerful model family proven to work exceptionally well in many different applications. Yet due to its ensembling nature, GBT is also hard to intrepret in general.

Here we demo lightgbm’s implementation of GBT with LIME explanation.

import lightgbm as lgb

ucihd_tr = lgb.Dataset(ucihd_X_train, label=ucihd_y_train)
ucihd_te = lgb.Dataset(ucihd_X_test, label=ucihd_y_test)

ucihd_lgb_params = {
  "learning_rate": .01,
  "boosting_type": "gbdt",
  "objective": "binary",
  "metric": ["binary_logloss", "auc"],
  "num_leaves": 4,
  "max_depth": 2,
  "min_data_per_leaf": 5,
  "verbose": -1,
  "seed": 64
}

ucihd_bst = lgb.train(
  params=ucihd_lgb_params,
  num_boost_round=300, early_stopping_rounds=20,
  train_set=ucihd_tr, valid_sets=[ucihd_te],
  verbose_eval=10)
Training until validation scores don't improve for 20 rounds
[10]    valid_0's binary_logloss: 0.662208  valid_0's auc: 0.742683
[20]    valid_0's binary_logloss: 0.637688  valid_0's auc: 0.837317
[30]    valid_0's binary_logloss: 0.612505  valid_0's auc: 0.836829
[40]    valid_0's binary_logloss: 0.590748  valid_0's auc: 0.862195
[50]    valid_0's binary_logloss: 0.573202  valid_0's auc: 0.86561
[60]    valid_0's binary_logloss: 0.558692  valid_0's auc: 0.871951
[70]    valid_0's binary_logloss: 0.545684  valid_0's auc: 0.870488
[80]    valid_0's binary_logloss: 0.53395   valid_0's auc: 0.877317
[90]    valid_0's binary_logloss: 0.524152  valid_0's auc: 0.876585
[100]   valid_0's binary_logloss: 0.514324  valid_0's auc: 0.879268
[110]   valid_0's binary_logloss: 0.506591  valid_0's auc: 0.877317
[120]   valid_0's binary_logloss: 0.499578  valid_0's auc: 0.877073
Early stopping, best iteration is:
[100]   valid_0's binary_logloss: 0.514324  valid_0's auc: 0.879268
ucihd_lgb_yhat = ucihd_bst.predict(ucihd_X_test)
ucihd_lgb_pred = (ucihd_lgb_yhat > .5).astype(int)

print(classification_report(ucihd_y_test, ucihd_lgb_pred))
              precision    recall  f1-score   support

           0       0.85      0.80      0.82        50
           1       0.77      0.83      0.80        41

    accuracy                           0.81        91
   macro avg       0.81      0.81      0.81        91
weighted avg       0.82      0.81      0.81        91
print(roc_auc_score(ucihd_y_test, ucihd_lgb_yhat))
0.8792682926829268

In this particular (rather small) dataset RF indeed outperforms GBT. As a matter of fact, based on existing benchmark a simple logistic regression may have a even higher score for this problem. Nevertheless, let’s move on to our explanation model with LIME:

def ucihd_lgb_predict_fn(x):
  # We need to output 2 columns for binary prob prediction.
  p = ucihd_bst.predict(x).reshape(-1, 1)
  return np.hstack((1 - p, p))

ucihd_lgb_explainer = LimeTabularExplainer(
  ucihd_X_train.values, class_names=["Negative", "Positive"],
  feature_names=ucihd_2.columns,
  categorical_features=cat_ind)

# We take the same examples previously explained in our RF explanation model.
ucihd_lgb_tp_exp = ucihd_lgb_explainer.explain_instance(
  ucihd_X_test.iloc[ucihd_rf_tp_idx[0]], ucihd_lgb_predict_fn, num_features=4)
ucihd_lgb_fp_exp = ucihd_lgb_explainer.explain_instance(
  ucihd_X_test.iloc[ucihd_rf_fp_idx[0]], ucihd_lgb_predict_fn, num_features=4)

ucihd_lgb_tp_exp.save_to_file("/tmp/explain_tab_lgb_tp.html")
ucihd_lgb_fp_exp.save_to_file("/tmp/explain_tab_lgb_fp.html")

TODO: Discussion on the explanation.

Optimized Categorical Encoding in lightgbm

This section is a digression on lightgbm usage.

Since lime’s API requires us to prepare our dataset in one-hot encoding representation, our lightgbm code use the same data pipeline as in scikit-learn random forest. But that is actually not optimized for lightgbm. The following code chunk showcases the best practice of encoding categoricals in lightgbm: We don’t encode them at all!

# We leave both missings and categoricals as-is in the dataset.
ucihd_train, ucihd_test = train_test_split(ucihd, test_size=.3, random_state=64)
ucihd_tr = lgb.Dataset(
  ucihd_train.drop("label", axis=1), label=ucihd_train["label"],
  categorical_feature=categorical_attr,
  free_raw_data=False)
ucihd_te = lgb.Dataset(
  ucihd_test.drop("label", axis=1), label=ucihd_test["label"],
  categorical_feature=categorical_attr,
  free_raw_data=False)

ucihd_bst_2 = lgb.train(
  params=ucihd_lgb_params,
  num_boost_round=300, early_stopping_rounds=20,
  train_set=ucihd_tr, valid_sets=[ucihd_te],
  verbose_eval=-1)
Training until validation scores don't improve for 20 rounds
Early stopping, best iteration is:
[100]   valid_0's binary_logloss: 0.514324  valid_0's auc: 0.879268
ucihd_lgb_yhat = ucihd_bst_2.predict(ucihd_test.drop("label", axis=1))
ucihd_lgb_pred = (ucihd_lgb_yhat > .5).astype(int)

print(roc_auc_score(ucihd_test["label"], ucihd_lgb_yhat))
0.8792682926829268

To summarize, There are two very special properties about lightgbm algorithm. lightgbm treats missings natively as a special tree split point. This allows us to keep the original missing as is and in many cases can result in better accuracy than imputation.6

In addition, lightgbm encodes categorical variables internally in a more efficient way. So we don’t even need to do one-hot encoding on our own. Of course in this tiny dataset we won’t see any noticable difference. But for large applications the impact can be huge. Whatever, by skipping one-hot encoding pipeline our code can be much neater as well.

3.3 On Image Classifier

TODO: Use a pre-trained model?

4 Shapley Regression Values

TODO: Theory Briefing here.

5 SHAP

Lundberg and Lee (2017) propose SHAP (SHapley Additive exPlanations), yet another additive feature attribution method for model explainability. It is a more general approach where LIME is indeed only a special case of it. Just like LIME, in theory it can be applied to any machine learning model, but comes with a customized fast implementation particularly for gradient boosting trees (GBT). It supports APIs of well-known GBT libraries such as xgboost, lightgbm, and catboost.

The interpretability provided by SHAP is again local. It assigns each feature an importance value for a particular prediction. Hence it provides for any given model prediction what may be the driving force for the model to make such prediction.

shap also comes with more visualization methods for feature investigation, especially for feature interaction exploration.

TODO: Theory Briefing here.

5.1 On Text Classifiers

5.1.1 Explain Random Forest

shap.TreeExplainer is optimized for GBT but not RF. For model with high dimensionality like a bag-of-words model it will suffer from high computation cost for non-GBT model. Hence we will skip the discussion on RF and move forward to a GBT implementation.

5.1.2 Explain Gradient Boosting Trees

In the previous section we didn’t train a GBT for the text classification problem. So let’s quickly build one such model first (with the same TF-IDF vectorization as we did for the random forest model).

# lightgbm does not allow utf-8 encoded feature names.
# Since important tokens are most likely ascii-compatible for our dataset,
# we simply strip non-ascii as a workaround for this exercise.
def remove_non_ascii(s):
  return "".join([i if ord(i) < 128 else "_" for i in s])

sorted_vocab_ascii = [remove_non_ascii(v) for v in sorted_vocab]

imdb_X_tr = lgb.Dataset(imdb_X_train, label=imdb_y_train, feature_name=sorted_vocab_ascii)
imdb_X_te = lgb.Dataset(imdb_X_test, label=imdb_y_test, feature_name=sorted_vocab_ascii)

imdb_lgb_params = {
  "learning_rate": .05,
  "boosting_type": "gbdt",
  "objective": "binary",
  "metric": ["binary_logloss", "auc"],
  "num_leaves": 16,
  "max_depth": 4,
  "min_data_per_leaf": 20,
  "verbose": -1
}

imdb_lgb_model_file = "models/text_clf_lgb.txt"

# Save/reload model to save notebook rendering time.
if os.path.exists(imdb_lgb_model_file):
  # TODO:
  # Parameters are not loaded back? A bug? (Which cause the subsequent call to shap_values fail.)
  # https://github.com/microsoft/LightGBM/issues/2613
  imdb_bst = lgb.Booster(model_file=imdb_lgb_model_file, params=imdb_lgb_params)
else:
  imdb_bst = lgb.train(
    params=imdb_lgb_params,
    num_boost_round=1000, early_stopping_rounds=20,
    train_set=imdb_X_tr, valid_sets=[imdb_X_te],
    verbose_eval=100)
  _ = imdb_bst.save_model(imdb_lgb_model_file)

imdb_lgb_yhat = imdb_bst.predict(imdb_X_test)
imdb_lgb_pred = (imdb_lgb_yhat > .5).astype(int)

print(classification_report(imdb_y_test, imdb_lgb_pred))
              precision    recall  f1-score   support

           0       0.88      0.85      0.86     12500
           1       0.85      0.88      0.87     12500

    accuracy                           0.86     25000
   macro avg       0.86      0.86      0.86     25000
weighted avg       0.86      0.86      0.86     25000
print(roc_auc_score(imdb_y_test, imdb_lgb_yhat))
0.9416203136

Just like RF we will have access to the overall feature importance with a GBT model:7

ax = lgb.plot_importance(imdb_bst, max_num_features=20)
plt.show()

Now for the explanation model, since shap.TreeExplainer is customized for GBT for speed, we can feed in all testing examples to calculate all shap values at once.

import shap

# Sparse matrix is supported by shap for lightgbm models.
imdb_lgb_explainer = shap.TreeExplainer(imdb_bst)
imdb_lgb_shap_values = imdb_lgb_explainer.shap_values(imdb_X_test)

def imdb_lgb_shap_plot(test_id, matplotlib=True):
  shap_plt = shap.force_plot(
    imdb_lgb_explainer.expected_value[1],
    imdb_lgb_shap_values[1][test_id,:],
    imdb_X_test[test_id,:].toarray(),  # We still need a dense matrix here.
    feature_names=sorted_vocab,
    matplotlib=matplotlib
  )
  return shap_plt

Global Importance

We can derive global importance based on shap values. Note that this is different from the loss/impurity or split time-based feature ranking derived from RF/GBT during training. It is an aggregation from all local prediction explanations (contributions) during testing data inference.

shap.summary_plot(imdb_lgb_shap_values, imdb_X_test, feature_names=sorted_vocab,
                  plot_type="bar", max_display=20, show=False)
plt.show()

Local Explanation

imdb_lgb_shap_plot(imdb_rf_tp_idx[0])

imdb_lgb_shap_plot(imdb_rf_fp_idx[0])

TODO: Discuss the result. Any thing different from LIME?

By default shap for lightgbm shows log-odds rather than probability in the plot. To verify this:

# Take the first true positive to examine:
p = imdb_bst.predict(imdb_X_test[imdb_rf_tp_idx[0],:].toarray())
print(p)
[0.71683258]
print(np.log(p / (1 - p)))
[0.92880398]

5.1.3 Explain Neural Nets with Word Embeddings

As of 2019-12-09 DeepExplainer does not yet support TF 2.0.8 And GradientExplainer is not well documented yet for TF 2.0. So we will use the KernelExplainer which is a implementation-agnostic explainer in shap. The compromise is that it will run very slow for each prediction.

imdb_exp_ind = np.array([imdb_rf_tp_idx[0], imdb_rf_fp_idx[0]])
# KernelExplainer.
def mm(X):
  return imdb_tr.predict_proba(X)[:,1]

imdb_nn_shap_explainer = shap.KernelExplainer(mm, seq_train_padded[:100])
# This is VERY slow...
imdb_nn_kernel_shap_values = imdb_nn_shap_explainer.shap_values(seq_test_padded[imdb_exp_ind])
# TODO:
# Contribution is attributed to original sequence input.
# In order to make explanation readable,
# we need to map each position to original word id then to word.

  0%|                                                                                            | 0/2 [00:00<?, ?it/s]
 50%|##########################################                                          | 1/2 [01:23<01:23, 83.47s/it]
100%|####################################################################################| 2/2 [02:48<00:00, 83.96s/it]
100%|####################################################################################| 2/2 [02:48<00:00, 84.29s/it]
# TODO: Makje sure everything works here.

# shap does not support keras model in scikit-learn wrapper.
# Let's re-build the model and retain its Sequental class.
dl_model = model_fn()
metrics = dl_model.fit(
  x=seq_train_padded, y=imdb_y_train,
  batch_size=256, epochs=20,
  validation_data=(seq_test_padded, imdb_y_test),
  validation_steps=20,
  callbacks=[
    tf.keras.callbacks.EarlyStopping(monitor="val_loss", patience=2),
    tf.keras.callbacks.ModelCheckpoint(tr_model_file, monitor="val_loss", save_best_only=True)
  ],
  verbose=0)

# DeepExplainer.
dl_shap_explainer = shap.DeepExplainer(dl_model, seq_train_padded)  # Wont' work.

# GradientExplainer.
imdb_nn_shap_explainer = shap.GradientExplainer(dl_model, seq_train_padded[:100])

imdb_nn_shap_explainer = shap.GradientExplainer(
  (imdb_tr.layers[0].input, imdb_tr.layers[-1].output),  # Not working for TF 2.0.
  seq_train_padded[:100])
imdb_nn_shap_explainer.shap_values(seq_test_padded[:3])  # Error here.

5.2 On Tabular Data Classifier

5.2.1 Explain Random Forest

ucihd_rf_explainer = shap.TreeExplainer(ucihd_rf)
ucihd_rf_shap_values = ucihd_rf_explainer.shap_values(ucihd_X_test)

def ucihd_rf_shap_plot(test_id, matplotlib=True):
  shap_plt = shap.force_plot(
    ucihd_rf_explainer.expected_value[1],
    ucihd_rf_shap_values[1][test_id,:],
    ucihd_X_test.iloc[[test_id]],
    matplotlib=matplotlib
  )
  return shap_plt

Global Feature Importance

Split-time-based feature ranking
ucihd_rf_feat_imp = pd.Series(ucihd_rf.feature_importances_, index=ucihd_X_train.columns).sort_values()
ax = ucihd_rf_feat_imp.tail(10).plot(kind="barh")
plt.show()

Shap value feature ranking
shap.summary_plot(ucihd_rf_shap_values, ucihd_X_train,
                  plot_type="bar", max_display=10, show=False)
plt.show()

Local Explanation

ucihd_rf_shap_plot(ucihd_rf_tp_idx[0])

ucihd_rf_shap_plot(ucihd_rf_fp_idx[0])

5.2.2 Explain Gradient Boosting Trees

For GBT we feed the model that is optimized, where categoricals are encoded internally without explicit one-hot encoding.

ucihd_lgb_explainer = shap.TreeExplainer(ucihd_bst_2)
ucihd_lgb_shap_values = ucihd_lgb_explainer.shap_values(ucihd_test.drop("label", axis=1))

def ucihd_lgb_shap_plot(test_id, matplotlib=True):
  shap_plt = shap.force_plot(
    ucihd_lgb_explainer.expected_value[1],
    ucihd_lgb_shap_values[1][test_id,:],
    ucihd_test.iloc[[test_id]].drop("label", axis=1),
    matplotlib=matplotlib
  )
  return shap_plt

Global Feature Importance

Split-time-based feature ranking
ax = lgb.plot_importance(ucihd_bst_2, max_num_features=10)
plt.show()

Shap value feature ranking
shap.summary_plot(ucihd_lgb_shap_values, ucihd_test.drop("label", axis=1),
                  plot_type="bar", max_display=10, show=False)
plt.show()

Local Explanation

ucihd_lgb_shap_plot(ucihd_rf_tp_idx[0])

ucihd_lgb_shap_plot(ucihd_rf_fp_idx[0])

5.2.3 The Impact of One-Hot Encoding On Explanation

As one may now realize, by explicitly one-hot-encode the categorical features we essentially split them into different features in their interpretable representation. This can be either good or bad, depending on the actual use case. From this particular aspect libary such as lightgbm provides the flexibility to allow us choose whether to do the one-hot encoding or not. So the way we want to construct the explanation model may well affect our implementation of the original model!

5.3 On Image Classifier

TODO: Use a pre-trained model?

6 Explainable Boosting Machine

Nori et al. (2019) publish the open source package interpret for a fast implementation of Generalized Additive Models with Pairwise Interactions, or GA2M (Lou et al. (2013)). As of 2019-12-09, interpret is still in its alpha release with limited documentation. The library contains two groups of modeling frameworks:

  • glassbox: explanable machine learning models
  • blackbox: machine learning explanation models (such as LIME and SHAP)

We’ve already covered the mainstream approach in the second group, i.e., models that approximate (locally) the original model (supposed to be a blackbox) for better explainability. The more interesting part of interpret is to bring about another type of model that is readily interpretable from its very origin, and yet still competitively accurate: the Explainable Boosting Machine, or EBM.

EBM is an additive model of the form:

\[ g(E(y)) = \beta_0 + \sum f_j (x_j) + \sum f_{ij}(x_i, x_j), \]

where \(g(\cdot)\) is a link function (sigmoid for binary classification, for an example), \(f_j\) is the feature function for the \(j\)-th feature, learned by a gradient boosting machine with only that feature at a time and in a round-robin fashion for all features. \(f_{ij}\) is a pairwise interaction feature function to further boost the accuracy of the model while remain interpretability.

The model is interpretable since the contribution of any individual feature can be directly quantified by their corresponding feature function \(f_j\). Such explanation can extend up to pairwise interaction if pairwise feature functions are also estimated.

TODO: How to detect pairwise interaction? Brief the FAST algorithm.

6.1 On Text/Image Data

EBM is not efficient for text dataset. Due to the algorithm’s design it will run too long for bag-of-words model since there are too many feature functions to estimate. If we fit a EBM with the movie review dataset, even if not a large dataset, we will encounter OOM (out-of-memory) issue. As a result, we will skip the discussion of EBM on a text classifier. (The same restriction applies to image dataset.)

6.2 On Tabular Data

ExplainableBoostingClassifier has a scikit-learn fashion API and hence is straightforward to use.

from interpret.glassbox import ExplainableBoostingClassifier

ucihd_ebm = ExplainableBoostingClassifier(
  n_estimators=16, feature_names=ucihd_2.columns, n_jobs=1)
_ = ucihd_ebm.fit(ucihd_X_train, ucihd_y_train)
WARNING: Logging before flag parsing goes to stderr.
W1209 23:23:00.540163 11636 all.py:334] Passing a numpy array to schema autogen when it should be dataframe.
ucihd_ebm_yhat = ucihd_ebm.predict_proba(ucihd_X_test)[:,1]
ucihd_ebm_pred = (ucihd_ebm_yhat > .5).astype(int)

print(classification_report(ucihd_y_test, ucihd_ebm_pred))
              precision    recall  f1-score   support

           0       0.88      0.88      0.88        50
           1       0.85      0.85      0.85        41

    accuracy                           0.87        91
   macro avg       0.87      0.87      0.87        91
weighted avg       0.87      0.87      0.87        91
print(roc_auc_score(ucihd_y_test, ucihd_ebm_yhat))
0.933170731707317

The model performs very well on the heart disease dataset, outperforming both RF and GBT.

6.2.1 Global Explanation

interpret comes with a rich set of visualization tools (with plotly as its backend). Model explanation is divided into two groups: global and local.

For global explanation, we have access to both global feature importance and a per-feature feature contribution stats.

ucihd_ebm_global = ucihd_ebm.explain_global()
# All feature info:
print(ucihd_ebm_global.selector)

# Global feature importance.
           Name         Type  # Unique  % Non-zero
0           age   continuous        40       1.000
1           sex  categorical         2       0.665
2      trestbps   continuous        45       1.000
3          chol   continuous       129       1.000
4       thalach   continuous        83       1.000
5       oldpeak   continuous        39       0.679
6         slope   continuous         3       1.000
7            ca   continuous         5       0.387
8        cp_1.0  categorical         2       0.080
9        cp_2.0  categorical         2       0.170
10       cp_3.0  categorical         2       0.292
11       cp_4.0  categorical         2       0.458
12       cp_nan  categorical         1       0.000
13      fbs_0.0  categorical         2       0.830
14      fbs_1.0  categorical         2       0.170
15      fbs_nan  categorical         1       0.000
16  restecg_0.0  categorical         2       0.505
17  restecg_1.0  categorical         2       0.014
18  restecg_2.0  categorical         2       0.481
19  restecg_nan  categorical         1       0.000
20    exang_0.0  categorical         2       0.670
21    exang_1.0  categorical         2       0.330
22    exang_nan  categorical         1       0.000
23     thal_3.0  categorical         2       0.571
24     thal_6.0  categorical         2       0.071
25     thal_7.0  categorical         2       0.349
26     thal_nan  categorical         2       0.009
ucihd_ebm_global.visualize().write_html("/tmp/ucihd_ebm_feat_imp.html", include_plotlyjs=False)

# Global contribution on the fisrt feature.
ucihd_ebm_global.visualize(0).write_html("/tmp/ucihd_ebm_age_imp.html", include_plotlyjs=False)

# Global contribution on the sencond feature.
ucihd_ebm_global.visualize(1).write_html("/tmp/ucihd_ebm_sex_imp.html", include_plotlyjs=False)

Feature Importance

Feature Contribution: Age

Feature Contribution: Gender

6.2.2 Local Explanation

More importantly, we must be able to explain a specific model prediction locally. This can also be done easily with a couple of lines:

# Explain the same instances previously on RF.
ucihd_exp_ind = np.array([ucihd_rf_tp_idx[0], ucihd_rf_fp_idx[0]])

# We can feed multiple examples at the same time.
ucihd_ebm_local = ucihd_ebm.explain_local(
  ucihd_X_test.iloc[ucihd_exp_ind,:], ucihd_y_test[ucihd_exp_ind])
ucihd_ebm_local.visualize(0).write_html("/tmp/ucihd_ebm_exp_tp.html", include_plotlyjs=False)
ucihd_ebm_local.visualize(1).write_html("/tmp/ucihd_ebm_exp_fp.html", include_plotlyjs=False)

7 References

Abadi, Martı́n, Ashish Agarwal, Paul Barham, Eugene Brevdo, Zhifeng Chen, Craig Citro, Greg S. Corrado, et al. 2015. “TensorFlow: Large-Scale Machine Learning on Heterogeneous Systems.” http://tensorflow.org/.

Lou, Yin, Rich Caruana, Johannes Gehrke, and Giles Hooker. 2013. “Accurate Intelligible Models with Pairwise Interactions.” In Proceedings of the 19th Acm Sigkdd International Conference on Knowledge Discovery and Data Mining, 623–31. ACM.

Lundberg, Scott M, and Su-In Lee. 2017. “A Unified Approach to Interpreting Model Predictions.” In Advances in Neural Information Processing Systems 30, edited by I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, 4765–74. Curran Associates, Inc. http://papers.nips.cc/paper/7062-a-unified-approach-to-interpreting-model-predictions.pdf.

Maas, Andrew L., Raymond E. Daly, Peter T. Pham, Dan Huang, Andrew Y. Ng, and Christopher Potts. 2011. “Learning Word Vectors for Sentiment Analysis.” In Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies, 142–50. Portland, Oregon, USA: Association for Computational Linguistics. http://www.aclweb.org/anthology/P11-1015.

Nori, Harsha, Samuel Jenkins, Paul Koch, and Rich Caruana. 2019. “InterpretML: A Unified Framework for Machine Learning Interpretability.” arXiv Preprint arXiv:1909.09223.

Pedregosa, F., G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, et al. 2011. “Scikit-Learn: Machine Learning in Python.” Journal of Machine Learning Research 12: 2825–30.

Pennington, Jeffrey, Richard Socher, and Christopher Manning. 2014. “Glove: Global Vectors for Word Representation.” In Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (Emnlp), 1532–43.

Ribeiro, Marco Tulio, Sameer Singh, and Carlos Guestrin. 2016. “Why Should I Trust You?: Explaining the Predictions of Any Classifier.” In Proceedings of the 22nd Acm Sigkdd International Conference on Knowledge Discovery and Data Mining, 1135–44. ACM.

Ushey, Kevin, JJ Allaire, and Yuan Tang. 2019. Reticulate: Interface to ’Python’. https://CRAN.R-project.org/package=reticulate.


  1. Some people will further differentiate explainability from interpretability, by characterizing interpretability as knowing how without knowing why, and explainability as not only knowing how but also knowing why. In this notebook for simplicity we don’t take such approach.↩︎

  2. In many such methods, the simplified input is the indicator of feature presence. One example: Shapley regression values.↩︎

  3. Keras also comes with the dataset preprocessed as integer sequences (from tf.keras.datasets import imdb).↩︎

  4. It will be much faster if we choose xgboost’s or lightgbm’s implementation of random forest. However, to demonstrate compatibility of lime with scikit-learn we purposely choose the slower implementation here.↩︎

  5. V.A. Medical Center, Long Beach and Cleveland Clinic Foundation:Robert Detrano, M.D., Ph.D.↩︎

  6. xgboost is the first to introduce such missing treatment among all the GBT package. lightgbm follows.↩︎

  7. By default lightgbm calculate the importance by counting how many times a feature contribute to an optimal split during model training. It also supports the impurity-based approach with argument importance_type set to "gain".↩︎

  8. https://github.com/slundberg/shap/issues/850.↩︎

LS0tCnRpdGxlOiAiT24gTW9kZWwgRXhwbGFpbmFiaWxpdHkiCnN1YnRpdGxlOiAiRnJvbSBMSU1FLCBTSEFQLCB0byBFeHBsYWluYWJsZSBCb29zdGluZyIKYXV0aG9yOgotIG5hbWU6IEt5bGUgQ2h1bmcKICBhZmZpbGlhdGlvbjoKZGF0ZTogImByIGZvcm1hdChTeXMudGltZSgpLCAnJWQgJWIgJVknKWAgTGFzdCBVcGRhdGVkICgwOSBEZWMgMjAxOSBGaXJzdCBVcGxvYWRlZCkiCm91dHB1dDoKICBodG1sX25vdGVib29rOgogICAgaGlnaGxpZ2h0OiB0YW5nbwogICAgbnVtYmVyX3NlY3Rpb25zOiB5ZXMKICAgIHRoZW1lOiBwYXBlcgogICAgdG9jOiB5ZXMKICAgIHRvY19kZXB0aDogMwogICAgdG9jX2Zsb2F0OiB5ZXMKICAgIGluY2x1ZGVzOgogICAgICBpbl9oZWFkZXI6IC90bXAvbWV0YV9oZWFkZXIuaHRtbAogIGNvZGVfZG93bmxvYWQ6IHRydWUKYmlibGlvZ3JhcGh5OiBtb2RlbF9leHBsYWluLmJpYgpub2NpdGU6IHwKICBAcmV0aWN1bGF0ZQogIEBtYWFzLUV0QWw6MjAxMTpBQ0wtSExUMjAxMQogIEBzY2lraXQtbGVhcm4KICBAdGVuc29yZmxvdzIwMTUtd2hpdGVwYXBlcgphYnN0cmFjdDogfAogIE1vZGVsIGV4cGxhaW5hYmlsaXR5IGhhcyBnYWluZWQgbW9yZSBhbmQgbW9yZSBhdHRlbnRpb24gcmVjZW50bHkgYW1vbmcgbWFjaGluZSBsZWFybmluZyBwcmFjdGl0aW9uZXJzLiBFc3BlY2lhbGx5IHdpdGggdGhlIHBvcHVsYXJpemF0aW9uIG9mIGRlZXAgbGVhcm5pbmcgZnJhbWV3b3Jrcywgd2hpY2ggZnVydGhlciBwcm9tb3RlcyB0aGUgdXNlIG9mIGluY3JlYXNpbmdseSBjb21wbGljYXRlZCBtb2RlbHMgdG8gaW1wcm92ZSBhY2N1cmFjeS4gSW4gdGhlIHJlYWxpdHksIGhvd2V2ZXIsIG1vZGVsIHdpdGggdGhlIGhpZ2hlc3QgYWNjdXJhY3kgbWF5IG5vdCBiZSB0aGUgb25lIHRoYXQgY2FuIGJlIGRlcGxveWVkLiBUcnVzdCBpcyBvbmUgaW1wb3J0YW50IGZhY3RvciBhZmZlY3RpbmcgdGhlIGFkb3B0aW9uIG9mIGNvbXBsaWNhdGVkIG1vZGVscy4gSW4gdGhpcyBub3RlYm9vayB3ZSBnaXZlIGEgYnJpZWYgaW50cm9kdWN0aW9uIHRvIHNldmVyYWwgcG9wdWxhciBtZXRob2RzIG9uIG1vZGVsIGV4cGxhaW5hYmlsaXR5LiBBbmQgd2UgZm9jdXMgbW9yZSBvbiB0aGUgaGFuZHMtb24gd2hpY2ggZGVtb25zdHJhdGVzIGhvdyB3ZSBjYW4gYWN0dWFsbHkgZXhwbGFpbiBhIG1vZGVsLCB1bmRlciBhIHZhcmlldHkgb2YgdXNlIGNhc2VzLgotLS0KPCEtLUZvciBlcXVhdGlvbiByZWZlcmVuY2UgaW4gUm1kLi0tPgo8c2NyaXB0IHR5cGU9InRleHQveC1tYXRoamF4LWNvbmZpZyI+Ck1hdGhKYXguSHViLkNvbmZpZyh7CiAgVGVYOiB7IGVxdWF0aW9uTnVtYmVyczogeyBhdXRvTnVtYmVyOiAiQU1TIiB9IH0KfSk7Cjwvc2NyaXB0PgoKPCEtLSBFbWJlZCBsaW1lIGphdmFzY3JpcHQgbGlicmFyeSBmb3IgZXhwbGFuYXRpb24gdmlzdWFsaXphdGlvbi4gLS0+CjxzY3JpcHQgc3JjPSJsaW1lLmpzIj48L3NjcmlwdD4KCjwhLS0gRW1iZWQgcGxvdGx5IGphdmFzY3JpcHQgbGlicmFyeS4KICBUaGlzIGlzIHRoZSBiYWNrZW5kIGZvciBpbnRlcnByZXRNTCB2aXN1YWxpemF0aW9uLgotLT4KPHNjcmlwdCBzcmM9Ii4uLy4uLy4uL3NpdGVfbGlicy91dGlscy9wbG90bHktMS41MS4xLm1pbi5qcyI+PC9zY3JpcHQ+CgpgYGB7ciBtZXRhLCBpbmNsdWRlPUZBTFNFfQptZXRhX2hlYWRlcl9maWxlIDwtIGZpbGUoIi90bXAvbWV0YV9oZWFkZXIuaHRtbCIpCgojIEFkZCBvcGVuIGdyYXBoIG1ldGEuCm1ldGEgPC0gYygKICAnPG1ldGEgbmFtZT0iYXV0aG9yIiBjb250ZW50PSJLeWxlIENodW5nIj4nLAogICc8bWV0YSBwcm9wZXJ0eT0ib2c6dGl0bGUiIGNvbnRlbnQ9Ik9uIE1vZGVsIEV4cGxhaW5hYmlsaXR5OiBGcm9tIFNoYXAsIExpbWUsIHRvIEludGVycHJldGFibGUgQm9vc3RpbmciPicsCiAgJzxtZXRhIHByb3BlcnR5PSJvZzp0eXBlIiBjb250ZW50PSJhcnRpY2xlIj4nLAogICc8bWV0YSBwcm9wZXJ0eT0ib2c6dXJsIiBjb250ZW50PSJodHRwczovL2V2ZXJkYXJrLmdpdGh1Yi5pby9rOS9ub3RlYm9va3MvbWwvbW9kZWxfZXhwbGFpbi9tb2RlbF9leHBsYWluLm5iLmh0bWwiPicsCiAgJzxtZXRhIHByb3BlcnR5PSJvZzppbWFnZSIgY29udGVudD0iaHR0cHM6Ly9ldmVyZGFyay5naXRodWIuaW8vazkvYXNzZXRzL2FuZHJvaWRpZnkuanBnIj4nLAogICc8bWV0YSBwcm9wZXJ0eT0ib2c6ZGVzY3JpcHRpb24iIGNvbnRlbnQ9IkEgZGF0YSBzY2llbmNlIG5vdGVib29rIGFib3V0IG1hY2hpbmUgbGVhcm5pbmcgbW9kZWwgZXhwbGFpbmFiaWxpdHkuIj4nCikKY29udGVudHMgPC0gbWV0YQoKIyBBZGQgR2l0aHViIGNvcm5lci4KZ2l0aHViX2Nvcm5lcl9zdmcgPC0gIi4uLy4uLy4uL2Fzc2V0cy9naXRodWJfY29ybmVyLmh0bWwiCmdpdGh1Yl9jb3JuZXJfY29uZiA8LSBsaXN0KGdpdGh1Yl9saW5rPSJodHRwczovL2dpdGh1Yi5jb20vZXZlcmRhcmsvazkvdHJlZS9tYXN0ZXIvbm90ZWJvb2tzL21sL21vZGVsX2V4cGxhaW4iKQpjb250ZW50cyA8LSBjKGNvbnRlbnRzLCBzdHJpbmdyOjpzdHJfaW50ZXJwKHJlYWRMaW5lcyhnaXRodWJfY29ybmVyX3N2ZyksIGdpdGh1Yl9jb3JuZXJfY29uZikpCndyaXRlTGluZXMoY29udGVudHMsIG1ldGFfaGVhZGVyX2ZpbGUpCgpjbG9zZShtZXRhX2hlYWRlcl9maWxlKQpgYGAKCmBgYHtyIHNldHVwLCBpbmNsdWRlPUZBTFNFfQpsaWJyYXJ5KHJldGljdWxhdGUpCnIgPC0gdHJ5KHVzZV9weXRob24oU3lzLmdldGVudigiUFlUSE9OX1BBVEgiKSwgcmVxdWlyZWQ9VFJVRSksIHNpbGVudD1UUlVFKQppZiAoIGlzKHIsICJ0cnktZXJyb3IiKSApIHsKICByIDwtIHRyeSh1c2VfdmlydHVhbGVudihTeXMuZ2V0ZW52KCJQWVRIT05fUEFUSCIpLCByZXF1aXJlZD1UUlVFKSwgc2lsZW50PVRSVUUpCiAgaWYgKCBpcyhyLCAidHJ5LWVycm9yIikgKSB1c2VfY29uZGFlbnYoU3lzLmdldGVudigiUFlUSE9OX1BBVEgiKSwgcmVxdWlyZWQ9VFJVRSkKfQoKIyBVdGlsaXR5IHRvIHBvc3QtcHJvY2VzcyBodG1sIG91dHB1dC4KbGlicmFyeSh4bWwyKQoKd3JpdGVfbGltZV9qcyA8LSBmdW5jdGlvbihpbmZpbGUpIHsKICAjIGxpbWUgaHRtbCBvdXRwdXQgY29udGFpbnMgYSBodWdlIGpzIHN0cmluZywKICAjIHRvIHJlZHVjZSBub3RlYm9vayBmaWxlIHNpemUgd2Ugb25seSB3YW50IHRvIGRlY2xhcmUgdGhlIGpzIG9uY2UuCiAgb3V0ZmlsZSA8LSAibGltZS5qcyIKICBkb2MgPC0gYXNfbGlzdChyZWFkX2h0bWwoaW5maWxlKSkKICBqc19zdHIgPC0gZG9jJGh0bWwkaGVhZCRzY3JpcHRbWzFdXQogICMgVXNlIGg0IGZvciB0ZXh0IGV4YW1wbGUgaGVhZGVyIHRvIGF2b2lkIGJlaW5nIGluY2x1ZGVkIGluIHJtZCB0b2MuCiAganNfc3RyIDwtIGdzdWIoImgzIiwgImg0IiwganNfc3RyKQogIHdyaXRlTGluZXMoanNfc3RyLCBvdXRmaWxlLCB1c2VCeXRlcz1UUlVFKQp9CgpwYXJzZV9saW1lX2h0bWxfb3V0cHV0IDwtIGZ1bmN0aW9uKGluZmlsZSwgZXhjbHVkZV9qcz1UUlVFKSB7CiAgb3V0ZmlsZSA8LSB0ZW1wZmlsZSgpCiAgZG9jIDwtIHJlYWRfaHRtbChpbmZpbGUpCiAgaWYgKCBleGNsdWRlX2pzICkgeG1sX3JlbW92ZSh4bWxfY2hpbGQoZG9jKSkKICB3cml0ZV9odG1sKGRvYywgb3V0ZmlsZSkKICBvdXRmaWxlCn0KYGBgCgotLS0KClRoaXMgbm90ZWJvb2sgaXMgd3JpdHRlbiB3aXRoIFtgcmV0aWN1bGF0ZWBdKGh0dHBzOi8vZ2l0aHViLmNvbS9yc3R1ZGlvL3JldGljdWxhdGUpLAphIHBhY2thZ2UgdGhhdCBhbGxvd3MgaW50ZXItb3BlcmF0aW9uIGJldHdlZW4gUiBhbmQgUHl0aG9uLgoKLS0tCgojIE1vdGl2YXRpb24KCldoeSBkbyB3ZSBuZWVkIHRvIGV4cGxhaW4gYSBtYWNoaW5lIGxlYXJuaW5nIG1vZGVsPwpUaGUgYmVuZWZpdCBvZiBhbiBleHBsYW5hYmxlIG1vZGVsIGFnYWluc3QgYSBibGFjay1ib3ggbW9kZWwgaXMgZm9yIHRoZSBtb2RlbCB0byBiZSAqdHJ1c3RlZCouClRydXN0IGNhbiBiZSBpbXBvcnRhbnQgaW4gbWFueSByZWFsIGFwcGxpY2F0aW9ucyB3aGVyZSB0aGUgc3VjY2Vzc2Z1bCBkZXBsb3ltZW50IG9mIGEgbWFjaGluZSBsZWFybmluZyBtb2RlbCByZXF1aXJlcyB0aGUgdHJ1c3QgZnJvbSBlbmQgdXNlcnMuClNvbWV0aW1lcyB0cnVzdCBwbGF5cyBhIGV2ZW4gYmlnZ2VyIHJvbGUgdGhhbiBtb2RlbCBhY2N1cmFjeS4KCk90aGVyIHRoYW4gdHJ1c3QsCm1vZGVsIGV4cGxhaW5hYmlsaXR5IChvciBpbnRlcnByZXRhYmlsaXR5LCBpbnRlcmNoYW5nZWFibHkgdXNlZCBoZXJlYWZ0ZXIpIG1heSBhbHNvIGd1aWRlIHVzIGluIHRoZSBjb3JyZWN0IGRpcmVjdGlvbiB0byBmdXJ0aGVyIGltcHJvdmUgdGhlIG1vZGVsLgpeW1NvbWUgcGVvcGxlIHdpbGwgZnVydGhlciBkaWZmZXJlbnRpYXRlIGV4cGxhaW5hYmlsaXR5IGZyb20gaW50ZXJwcmV0YWJpbGl0eSwKYnkgY2hhcmFjdGVyaXppbmcgaW50ZXJwcmV0YWJpbGl0eSBhcyBrbm93aW5nIGhvdyB3aXRob3V0IGtub3dpbmcgd2h5LAphbmQgZXhwbGFpbmFiaWxpdHkgYXMgbm90IG9ubHkga25vd2luZyBob3cgYnV0IGFsc28ga25vd2luZyB3aHkuCkluIHRoaXMgbm90ZWJvb2sgZm9yIHNpbXBsaWNpdHkgd2UgZG9uJ3QgdGFrZSBzdWNoIGFwcHJvYWNoLl0KCkluIGdlbmVyYWwsCmxpbmVhciBtb2RlbCBpcyBtb3JlIGludGVycHJldGFibGUgdGhhbiBub24tbGluZWFyIG1vZGVsLgpCdXQgdGhlIGZvcm1lciBhbHNvIHN1ZmZlcnMgZnJvbSBsb3dlciBhY2N1cmFjeS4KTW9yZSBhZHZhbmNlZCBhbmQgaGVuY2UgY29tcGxpY2F0ZWQgbW9kZWwgdXN1YWxseSBoYXMgd29yc2UgaW50ZXJwcmV0YWJpbGl0eS4KCk9uZSBzaG91bGQgbm90IGNvbmZ1c2UgbW9kZWwgZXhwbGFpbmFiaWxpdHkgd2l0aCB0aGUgYWN0dWFsIGNhdXNhbGl0eS4KQmVpbmcgYWJsZSB0byBleHBsYWluIGEgbW9kZWwgZG9lc24ndCBtZWFuIHRoYXQgd2UgY2FuIGlkZW50aWZ5IGFueSBncm91bmQtdHJ1dGggY2F1c2FsIHJlbGF0aW9uIGJlaGluZCB0aGUgbW9kZWwuCk1vZGVsIGV4cGxhaW5hYmlsaXR5IGlzIGZvciBhbmQgb25seSBmb3IgdGhlIG1vZGVsLApidXQgbm90IGZvciB0aGUgZmFjdHMgd2UnZCBsaWtlIHRvIG1vZGVsLgpOZXZlcnRoZWxlc3MsCnVuZGVyc3RhbmQgaG93IHdlIGNhbiByZWFzb24gdGhlIG1vZGVsIGRlZmluaXRlbHkgd2lsbCBoZWxwIHVzIGJldHRlciBtb2RlbCB0aGUgYWN0dWFsIHBhdHRlcm4gYmVoaW5kIHRoZSBzY2VuY2UuCgpJbiB0aGlzIG5vdGVib29rIHdlIHdpbGwgd2FsayB0aHJvdWdoIDMgcG9wdWxhciBhcHByb2FjaGVzIG9mIG1vZGVsIHByZWRpY3Rpb24gZXhwbGFuYXRpb24sCmVhY2ggb2YgdGhlbSBjb21lcyB3aXRoIGEgZGVkaWNhdGVkIFB5dGhvbiBwYWNrYWdlOgoKMS4gW2BzaGFwYF0oaHR0cHM6Ly9naXRodWIuY29tL3NsdW5kYmVyZy9zaGFwKQoyLiBbYGxpbWVgXShodHRwczovL2dpdGh1Yi5jb20vbWFyY290Y3IvbGltZSkKMy4gW2BpbnRlcnByZXRgXShodHRwczovL2dpdGh1Yi5jb20vaW50ZXJwcmV0bWwvaW50ZXJwcmV0KQoKIyBFeHBsYW5hdGlvbiBNb2RlbHMKCkFuIGV4cGxhbmF0aW9uIG1vZGVsICRnKHgpJCBpcyBhbiAqaW50ZXJwcmV0YWJsZSBhcHByb3hpbWF0aW9uKiBvZiB0aGUgb3JpZ2luYWwgbW9kZWwgJGYoeCkkLgpJdHMgc29sZSBwdXJwb3NlIGlzIHRvIGdpdmUgZXh0cmEgZXhwbGFpbmFiaWxpdHkgdGhlIG9yaWdpbmFsIG1vZGVsIGZhaWxzIHRvIHByb3ZpZGUsCmR1ZSB0byBpdHMgb3duIGNvbXBsZXhpdHkuCgpUaGUgZ2VuZXJhbCBpZGVhIGlzIHRvIHVzZSBhIHNpbXBsaWZpZWQgaW5wdXQgJHhccHJpbWUkIHN1Y2ggdGhhdCAkeCA9IGhfeCh4XHByaW1lKSQsCndoZXJlICRoX3goXGNkb3QpJCBpcyBhIG1hcHBpbmcgZnVuY3Rpb24gZm9yIGFueSBnaXZlbiByYXcgaW5wdXQgJHgkLgpUaGVuIHRoZSBpbnRlcnByZXRhYmxlIGFwcHJveGltYXRpb24gY2FuIGJlIHdyaXR0ZW4gYXM6CgokJApnKHhccHJpbWUpIFxhcHByb3ggZihoX3goeFxwcmltZSkpLgokJAoKVGhlICphZGRpdGl2ZSBmZWF0dXJlIGF0dHJpYnV0aW9uIG1ldGhvZHMqIHNwZWNpZnkgdGhlIGV4cGxhbmF0aW9uIG1vZGVsIG9mIHRoZSBmb2xsb3dpbmcgZm9ybToKCiQkCmcoeFxwcmltZSkgPSBccGhpXzAgKyBcc3VtX3tpID0gMX1ebSBccGhpX2kgeF9pXHByaW1lLAokJAoKd2hlcmUgJG0kIGlzIHRvdGFsIG51bWJlciBvZiBzaW1wbGlmaWVkIGZlYXR1cmVzLAokeFxwcmltZSBcaW4gXHswLCAxXH0kIHNpbXBseSBhbiBpbmRpY2F0b3IuXltJbiBtYW55IHN1Y2ggbWV0aG9kcywgdGhlIHNpbXBsaWZpZWQgaW5wdXQgaXMgdGhlIGluZGljYXRvciBvZiBmZWF0dXJlIHByZXNlbmNlLiBPbmUgZXhhbXBsZTogU2hhcGxleSByZWdyZXNzaW9uIHZhbHVlcy5dCkFwcGFyZW50bHksCnRoZSBjaG9pY2Ugb2YgYW4gYWRkaXRpdmUgbW9kZWwgaXMgZm9yIChsaW5lYXIpIGludHJlcHJldGFiaWxpdHkuClRoZSBzaW1wbGlmaWVkIGZlYXR1cmVzIGFyZSBhbiAqaW50ZXJwcmV0YWJsZSByZXByZXNlbnRhdGlvbiogb2YgdGhlIG9yaWdpbmFsIG1vZGVsIGZlYXR1cmVzLgoKIyBMSU1FCgpPbmUgdmVyeSBwb3B1bGFyIHN1Y2ggYWJvdmUgYWRkaXRpdmUgbW9kZWwgaXMgTElNRSAoQHJpYmVpcm8yMDE2c2hvdWxkKS4KTElNRSBzdGFuZHMgZm9yICoqTG9jYWwgSW50ZXJwcmV0YWJsZSBNb2RlbC1BZ25vc3RpYyBFeHBsYW5hdGlvbnMuKioKQXMgaXRzIGZ1bGwgbmFtZSBzdWdnZXN0cywKTElNRSBjYW4gYmUgYXBwbGllZCB0byAqYW55KiBtYWNoaW5lIGxlYXJuaW5nIG1vZGVsLgpMSU1FIGFjaGlldmVzIHByZWRpY3Rpb24tbGV2ZWwgaW50ZXJwcmV0YWJpbGl0eSBieSBhcHByb3htaWF0aW5nIHRoZSBvcmlnaW5hbCBtb2RlbCB3aXRoIGFuIGV4cGxhbmF0aW9uIG1vZGVsIGxvY2FsbHkgYXJvdW5kIHRoYXQgcHJlZGljdGlvbi4KCioqVE9ETzogQWRkIHRoZW9yeSBicmllZmluZyBoZXJlLioqCgojIyBPbiBUZXh0IENsYXNzaWZpZXJzCgpGb3IgdGV4dCBjbGFzc2lmaWNhdGlvbiBwcm9ibGVtLAp0aGUgbW9zdCBzdHJhaWdodGZvcndhcmQgaW50ZXJwcmV0YWJsZSByZXByZXNlbnRhdGlvbiBvZiB0aGUgbW9kZWwgZmVhdHVyZXMgd2lsbCBiZSBhIGJpbmFyeSBpbmRpY2F0b3IgdmVjdG9yIG9mIGJhZyBvZiB3b3Jkcy4KU28gdGhlIGV4cGxhbmF0aW9uIG1vZGVsIHdpbGwgdHJ5IHRvIHJlYXNvbiB3aGljaCB3b3JkIG9yIHRva2VuIGlzIGRyaXZpbmcgdGhlIHByZWRpY3Rpb24gaW4gd2hhdCBkaXJlY3Rpb24uCkFuZCB0aGlzIGlzIHRydWUgbm8gbWF0dGVyIHRoZSBmb3JtIG9mIHRoZSBvcmlnaW5hbCBtb2RlbCBmZWF0dXJlLgpNYXkgaXQgYmUgYSB3b3JkIGNvdW50IG1hdHJpeCwKYSB0ZXJtIGZyZXF1ZW5jeS1pbnZlcnNlIGRvY3VtZW50IGZyZXF1ZW5jeSAoVEYtSURGKSBtYXRyaXgsCm9yIG51bWVyaWNhbCBlbWJlZGRpbmdzLgoKSW4gdGhlIGZvbGxvd2luZyB3ZSB3aWxsIHVzZSBbTGFyZ2UgTW92aWUgUmV2aWV3IERhdGFzZXRdKGh0dHBzOi8vYWkuc3RhbmZvcmQuZWR1L35hbWFhcy9kYXRhL3NlbnRpbWVudC8pIHRvIGRvIGEgYmluYXJ5IHNlbnRpbWVudCBjbGFzc2lmaWNhdGlvbiBleGVyY2lzZS4KV2Ugd2lsbCB1c2UgbWFjaGluZSBsZWFybmluZyBsaWJyYXJpZXMgc3VjaCBhcyBgc2Npa2l0LWxlYXJuYCBhbmQgYHRlbnNvcmZsb3dgIHRvIHF1aWNrbHkgYnVpbGQgbW9kZWxzIGFuZCB1c2UgYGxpbWVgIHRvIGV4cGVyaW1lbnQgZXhwbGFuYXRpb24gbW9kZWxpbmcuCgpgYGB7cHl0aG9uIGltcG9ydF9zb21lfQppbXBvcnQgb3MKaW1wb3J0IGxvZ2dpbmcKbG9nZ2luZy5nZXRMb2dnZXIoInRlbnNvcmZsb3ciKS5zZXRMZXZlbChsb2dnaW5nLkVSUk9SKQppbXBvcnQgd2FybmluZ3MKd2FybmluZ3Muc2ltcGxlZmlsdGVyKGFjdGlvbj0iaWdub3JlIiwgY2F0ZWdvcnk9VXNlcldhcm5pbmcpCndhcm5pbmdzLnNpbXBsZWZpbHRlcihhY3Rpb249Imlnbm9yZSIsIGNhdGVnb3J5PUZ1dHVyZVdhcm5pbmcpCgppbXBvcnQgbWF0cGxvdGxpYi5weXBsb3QgYXMgcGx0CmltcG9ydCBudW1weSBhcyBucAppbXBvcnQgcGFuZGFzIGFzIHBkCgppbXBvcnQgdGVuc29yZmxvdyBhcyB0ZgpwcmludCh0Zi5fX3ZlcnNpb25fXykKaWYgdGYudGVzdC5pc19ncHVfYXZhaWxhYmxlKCk6CiAgcHJpbnQodGYudGVzdC5ncHVfZGV2aWNlX25hbWUoKSkKCmltcG9ydCBza2xlYXJuCmZyb20gc2tsZWFybi5mZWF0dXJlX2V4dHJhY3Rpb24udGV4dCBpbXBvcnQgVGZpZGZWZWN0b3JpemVyCmZyb20gc2tsZWFybi5lbnNlbWJsZSBpbXBvcnQgUmFuZG9tRm9yZXN0Q2xhc3NpZmllcgpmcm9tIHNrbGVhcm4ucGlwZWxpbmUgaW1wb3J0IG1ha2VfcGlwZWxpbmUKZnJvbSBza2xlYXJuLm1ldHJpY3MgaW1wb3J0IGNsYXNzaWZpY2F0aW9uX3JlcG9ydCwgcm9jX2F1Y19zY29yZQpmcm9tIHNrbGVhcm4ubW9kZWxfc2VsZWN0aW9uIGltcG9ydCB0cmFpbl90ZXN0X3NwbGl0CmltcG9ydCBqb2JsaWIKCnByaW50KHNrbGVhcm4uX192ZXJzaW9uX18pCmBgYAoKYGBge3B5dGhvbiBta2Rpcn0KIyBDcmVhdGUgbW9kZWwgZGlyIHRvIGNhY2hlIGFsbCBtb2RlbHMgdHJhaW5lZCBpbiB0aGUgbm90ZWJvb2suCm1vZGVsX2RpciA9ICJtb2RlbHMiCmlmIG5vdCBvcy5wYXRoLmV4aXN0cyhtb2RlbF9kaXIpOgogICAgb3MubWFrZWRpcnMobW9kZWxfZGlyKQoKIyBEaXJlY3RvcnkgdG8gY2FjaGUgZGF0YXNldC4KaG9tZSA9IG9zLnBhdGguZXhwYW5kdXNlcigifiIpCmNhY2hlX2RpciA9IG9zLnBhdGguam9pbihob21lLCAiLmtlcmFzIikKYGBgCgpGaXJzdCwKd2UgcHJlcGFyZSB0aGUgbW92aWUgcmV2aWV3IGRhdGFzZXQuXltLZXJhcyBhbHNvIGNvbWVzIHdpdGggdGhlIGRhdGFzZXQgcHJlcHJvY2Vzc2VkIGFzIGludGVnZXIgc2VxdWVuY2VzIChgZnJvbSB0Zi5rZXJhcy5kYXRhc2V0cyBpbXBvcnQgaW1kYmApLl0KCmBgYHtweXRob24gbWF5YmVfZG93bmxvYWRfaW1kYiwgcmVzdWx0cz0iaGlkZSJ9CmltcG9ydCB0ZW5zb3JmbG93X2RhdGFzZXRzIGFzIHRmZHMKCiMgTG9hZCB0aGUgZGF0YSBhcyB0Zi5kYXRhLkRhdGFzZXQuCmltZGIgPSB0ZmRzLmxvYWQobmFtZT0iaW1kYl9yZXZpZXdzIiwgYXNfc3VwZXJ2aXNlZD1UcnVlLAogICAgICAgICAgICAgICAgIGRhdGFfZGlyPW9zLnBhdGguam9pbihob21lLCAidGVuc29yZmxvd19kYXRhc2V0cyIpKQpgYGAKClRoZSBkYXRhc2V0IGlzIGEgcGVyZmVjdGx5IGJhbGFuY2VkIGRhdGFzZXQgd2l0aCA1MCwwMDAgZXhhbXBsZXMsCmhhbGYgZm9yIHBvc2l0aXZlIGFuZCBoYWxmIGZvciBuZWdhdGl2ZSBzZW50aW1lbnQuCgpgYGB7cHl0aG9uIHByZXBhcmVfaW1kYn0KIyBFeHRyYWN0IGFsbCB0ZXh0cyBhcyBsaXN0IHNpbmNlIHdlIHdhbnQgdG8gdXNlIGxpYnJhcmllcyBvdGhlciB0aGFuIHRlbnNvcmZsb3cgYXMgd2VsbC4KIyBBbmQgc2luY2UgdGhpcyBpcyBhIHNtYWxsIGRhdGFzZXQsIHdlIGRvbid0IGNhcmUgYWJvdXQgbWVtb3J5IHVzYWdlLgojIFdlIHNraXAgdGhlIHVzZSBvZiBhIGRhdGFzZXQgaXRlcmF0b3IuCmltZGJfcmV2aWV3c190cmFpbiA9IFtdCmltZGJfcmV2aWV3c190ZXN0ID0gW10KaW1kYl95X3RyYWluID0gW10KaW1kYl95X3Rlc3QgPSBbXQpmb3IgeCwgeSBpbiBpbWRiWyJ0cmFpbiJdLmJhdGNoKDEyOCk6CiAgaW1kYl9yZXZpZXdzX3RyYWluLmV4dGVuZCh4Lm51bXB5KCkpCiAgaW1kYl95X3RyYWluLmV4dGVuZCh5Lm51bXB5KCkpCmZvciB4LCB5IGluIGltZGJbInRlc3QiXS5iYXRjaCgxMjgpOgogIGltZGJfcmV2aWV3c190ZXN0LmV4dGVuZCh4Lm51bXB5KCkpCiAgaW1kYl95X3Rlc3QuZXh0ZW5kKHkubnVtcHkoKSkKCiMgVEYgd29ya3Mgb24gYnl0ZXMsIGJ1dCBzb21lIG90aGVyIHBhY2thZ2VzIG1heSBvbmx5IHdvcmsgb24gZGVjb2RlZCBzdHJpbmcuCmltZGJfcmV2aWV3c190cmFpbiA9IFtiLmRlY29kZSgidXRmOCIpIGZvciBiIGluIGltZGJfcmV2aWV3c190cmFpbl0KaW1kYl9yZXZpZXdzX3Rlc3QgPSBbYi5kZWNvZGUoInV0ZjgiKSBmb3IgYiBpbiBpbWRiX3Jldmlld3NfdGVzdF0KaW1kYl95X3RyYWluID0gbnAuYXJyYXkoaW1kYl95X3RyYWluKQppbWRiX3lfdGVzdCA9IG5wLmFycmF5KGltZGJfeV90ZXN0KQoKIyBUYWtlIG9uZSByZXZpZXcuCnByaW50KGltZGJfcmV2aWV3c190cmFpbls4N10pCgpwcmludChpbWRiX3lfdHJhaW5bODddKSAgIyBMYWJlbC4gMCBhcyBuZWdhdGl2ZSBhbmQgMSBhcyBwb3NpdGl2ZS4KYGBgCgpXZSB1c2UgdGhlIGRhdGEgcHJlcGFyZWQgYnkgYHRlbnNvcmZsb3ctZGF0YXNldHNgIGhlcmUganVzdCB0byBzYXZlIHNvbWUgdGltZS4KRm9yIHRob3NlIHdobyB3YW50IHRvIHByb2Nlc3MgdGhlIGRhdGEgaW4gaXRzIHZlcnkgb3JpZ2luYWwgZm9ybWF0ICh3aGVyZSBvbmUgcmV2aWV3IGlzIGluIG9uZSBgLnR4dGAgZmlsZSksCnRoZSBmaWxlcyBjYW4gYmUgZG93bmxvYWRlZCBieSB0aGlzIHBpZWNlIG9mIGNvZGU6CgpgYGBweXRob24KaW1kYl9yZW1vdGVfcGF0aCA9ICJodHRwczovL2FpLnN0YW5mb3JkLmVkdS9+YW1hYXMvZGF0YS9zZW50aW1lbnQvYWNsSW1kYl92MS50YXIuZ3oiCmltZGJfZm5hbWUgPSBvcy5wYXRoLmJhc2VuYW1lKGltZGJfcmVtb3RlX3BhdGgpCmltZGJfbG9jYWxfcGF0aCA9IG9zLnBhdGguam9pbihjYWNoZV9kaXIsICJkYXRhc2V0cyIsIGltZGJfZm5hbWUpCgppZiBub3Qgb3MucGF0aC5leGlzdHMoaW1kYl9sb2NhbF9wYXRoKToKICBfID0gdGYua2VyYXMudXRpbHMuZ2V0X2ZpbGUoZm5hbWU9aW1kYl9mbmFtZSwgb3JpZ2luPWltZGJfcmVtb3RlX3BhdGgsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGV4dHJhY3Q9VHJ1ZSwgY2FjaGVfZGlyPWNhY2hlX2RpcikKYGBgCgojIyMgRXhwbGFpbiBSYW5kb20gRm9yZXN0CgpMZXQncyBidWlsZCBhIHJhbmRvbSBmb3Jlc3Qgd2l0aCBURi1JREYgYXMgb3VyIGZlYXR1cmUgc3BhY2UuCldlIHdpbGwgdXNlIHRoZSBwb3B1bGFyIGBzY2lraXQtbGVhcm5gIGxpYnJhcnkgZm9yIGltcGxlbWVudGF0aW9uLl5bSXQgd2lsbCBiZSBtdWNoIGZhc3RlciBpZiB3ZSBjaG9vc2UgYHhnYm9vc3RgJ3Mgb3IgYGxpZ2h0Z2JtYCdzIGltcGxlbWVudGF0aW9uIG9mIHJhbmRvbSBmb3Jlc3QuIEhvd2V2ZXIsIHRvIGRlbW9uc3RyYXRlIGNvbXBhdGliaWxpdHkgb2YgYGxpbWVgIHdpdGggYHNjaWtpdC1sZWFybmAgd2UgcHVycG9zZWx5IGNob29zZSB0aGUgc2xvd2VyIGltcGxlbWVudGF0aW9uIGhlcmUuXQoKYGBge3B5dGhvbiB0ZmlkZn0KIyBXZSBkcm9wIHdvcmRzIHRoYXQgYXJlIHRvbyBmcmVxdWVudCBvciB0b28gcmFyZSBpbiB0aGUgdHJhaW5pbmcgZGF0YXNldC4KaW1kYl92ZWN0b3JpemVyID0gVGZpZGZWZWN0b3JpemVyKGxvd2VyY2FzZT1UcnVlLCBtaW5fZGY9MTAsIG1heF9kZj0uOSkKaW1kYl9YX3RyYWluID0gaW1kYl92ZWN0b3JpemVyLmZpdF90cmFuc2Zvcm0oaW1kYl9yZXZpZXdzX3RyYWluKQppbWRiX1hfdGVzdCA9IGltZGJfdmVjdG9yaXplci50cmFuc2Zvcm0oaW1kYl9yZXZpZXdzX3Rlc3QpCnByaW50KGxlbihpbWRiX3ZlY3Rvcml6ZXIudm9jYWJ1bGFyeV8pKSAgIyBXaXRob3V0IE9PViB0b2tlbi4KYGBgCgpgYGB7cHl0aG9uIGltZGJfcmZ9CmltZGJfcmZfbW9kZWxfZmlsZSA9ICJtb2RlbHMvdGV4dF9yZi5qb2JsaWIiCgojIFNhdmUvcmVsb2FkIHRoZSBtb2RlbCB0byBzYXZlIG5vdGVib29rIHJlbmRlcmluZyB0aW1lLgppZiBvcy5wYXRoLmV4aXN0cyhpbWRiX3JmX21vZGVsX2ZpbGUpOgogIGltZGJfcmYgPSBqb2JsaWIubG9hZChpbWRiX3JmX21vZGVsX2ZpbGUpCmVsc2U6CiAgaW1kYl9yZiA9IFJhbmRvbUZvcmVzdENsYXNzaWZpZXIobl9lc3RpbWF0b3JzPTMwMCwgcmFuZG9tX3N0YXRlPTY0LCBuX2pvYnM9LTIpCiAgXyA9IGltZGJfcmYuZml0KGltZGJfWF90cmFpbiwgaW1kYl95X3RyYWluKQogIF8gPSBqb2JsaWIuZHVtcChpbWRiX3JmLCBpbWRiX3JmX21vZGVsX2ZpbGUpCgppbWRiX3JmX3ByZWQgPSBpbWRiX3JmLnByZWRpY3QoaW1kYl9YX3Rlc3QpCmltZGJfcmZfeWhhdCA9IGltZGJfcmYucHJlZGljdF9wcm9iYShpbWRiX1hfdGVzdClbOiwxXQoKcHJpbnQoY2xhc3NpZmljYXRpb25fcmVwb3J0KGltZGJfeV90ZXN0LCBpbWRiX3JmX3ByZWQpKQpwcmludChyb2NfYXVjX3Njb3JlKGltZGJfeV90ZXN0LCBpbWRiX3JmX3loYXQpKQpgYGAKCkFzIGEgYmFzZWxpbmUgd2l0aG91dCBleHRlbnNpdmUgdHVuaW5nICh3ZSBkaWRuJ3QgdHVuZSBhbnl0aGluZyBpbmRlZWQhKSwKcmFuZG9tIGZvcmVzdCBzZWVtcyB0byBwZXJmb3JtIGZhaXJseSB3ZWxsIG9uIHRoaXMgZGF0YXNldC4KCkFzIHBhcnQgb2YgdGhlIGFsZ29yaXRobSdzIGRlc2lnbiB3ZSBhcmUgYWJsZSB0byBkZXJpdmUgYSBnbG9iYWwgdmlldyBvZiBmZWF0dXJlIGltcG9ydGFuY2UuClRoaXMgaXMgYmFzZWQgb24gaG93IG11Y2ggZWFjaCBmZWF0dXJlIGNhbiByZWR1Y2UgdGhlIGltcHVyaXR5IGR1cmluZyBhbGwgdHJlZSBzcGxpdHRpbmdzLgpGb3IgZXhhbXBsZSwKd2UgY2FuIHBsb3QgdGhlIHRvcCAyMCBmZWF0dXJlczoKCmBgYHtweXRob24gaW1kYl9yZl9mZWF0X2ltcH0Kc29ydGVkX3ZvY2FiID0gc29ydGVkKGltZGJfdmVjdG9yaXplci52b2NhYnVsYXJ5Xy5pdGVtcygpLCBrZXk9bGFtYmRhIGt2OiBrdlsxXSkKc29ydGVkX3ZvY2FiID0gW3cgZm9yIHcsIGkgaW4gc29ydGVkX3ZvY2FiXQoKaW1kYl9yZl9mZWF0X2ltcCA9IHBkLlNlcmllcyhpbWRiX3JmLmZlYXR1cmVfaW1wb3J0YW5jZXNfLCBpbmRleD1zb3J0ZWRfdm9jYWIpLnNvcnRfdmFsdWVzKCkKYXggPSBpbWRiX3JmX2ZlYXRfaW1wLnRhaWwoMjApLnBsb3Qoa2luZD0iYmFyaCIpCnBsdC5zaG93KCkKYGBgCgpJbnRlcnByZXRhdGlvbiBvZiB0aGUgaW1wdXJpdHktYmFzZWQgcmFua2luZyBtdXN0IGJlIHZlcnkgY2FyZWZ1bCB0aG91Z2guCkZvciBleGFtcGxlLCByZWxhdGVkIGZlYXR1cmVzIHdpbGwgdGhlb3JldGljYWxseSBoYXZlIHNpbWlsYXIgaW1wYWN0IGJ1dCBvbmx5IG9uZSBvZiBpdCB3aWxsIGdhaW4gaGlnaGVyIHNjb3JlIChhbmQgc3VwcHJlc3MgdGhlIG90aGVyKSBpbiB0aGUgcmFua2luZy4KV2hpY2ggb25lIHN0YW5kcyBvdXQgaXMgdG90YWxseSByYW5kb20uCgpJbiBnZW5lcmFsIGl0IGlzIE5PVCByZWNvbW1lbmRlZCB0byB1c2UgaW1wdXJpdHkgb3IgZXZlbiBsb3NzLWJhc2VkIGZlYXR1cmUgcmFua2luZyB0byAqaW50ZXJwcmV0KiBhIHRyZWUgZW5zZW1ibGUgbW9kZWwuClN1Y2ggcmFua2luZyBpbmZvcm1hdGlvbiBpcyBzdGlsbCB1c2VmdWwgdG8gdW5kZXJzdGFuZCBkaWZmZXJlbnQgYXNwZWN0cyBvZiB0aGUgbW9kZWwsCmFuZCBjYW4gYmUgdXNlZCB0byBzdWJzZXQgZmVhdHVyZSB0byBjb3VudGVyIG92ZXItZml0dGluZyBpc3N1ZSwgaWYgYW55LgpCdXQgaXQgd29uJ3QgaGVscCByZWFsbHkgZXhwbGFpbiB0aGUgbW9kZWwgcGVyIHNlLgpBbmQgdGhpcyBpcyBleGFjdGx5IHdoeSB3ZSBuZWVkIGEgZXhwbGFuYXRpb24gbW9kZWwgaW4gdGhlIGZpcnN0IHBsYWNlLgoKTm93IG1vdmUgb24gdG8gbW9kZWwgZXhwbGFuYXRpb24gd2l0aCBMSU1FOgoKYGBge3B5dGhvbiBsaW1lX2ltZGJfcmZ9CmZyb20gbGltZS5saW1lX3RleHQgaW1wb3J0IExpbWVUZXh0RXhwbGFpbmVyCgojIFdlIG5lZWQgYSBwaXBlbGluZSBzaW5jZSBMaW1lVGV4dEV4cGxhaW5lci5leHBsYWluX2luc3RhbmNlIGV4cGVjdHMgcmF3IHRleHQgaW5wdXQuCmltZGJfcmZfcGlwZSA9IG1ha2VfcGlwZWxpbmUoaW1kYl92ZWN0b3JpemVyLCBpbWRiX3JmKQppbWRiX3JmX2V4cGxhaW5lciA9IExpbWVUZXh0RXhwbGFpbmVyKGNsYXNzX25hbWVzPVsiTmVnYXRpdmUiLCAiUG9zaXRpdmUiXSkKCmltZGJfcmZfdHBfaWR4ID0gbnAud2hlcmUobnAubG9naWNhbF9hbmQoaW1kYl9yZl9wcmVkID09IDEsIGltZGJfeV90ZXN0ID09IDEpKVswXQppbWRiX3JmX2ZwX2lkeCA9IG5wLndoZXJlKG5wLmxvZ2ljYWxfYW5kKGltZGJfcmZfcHJlZCA9PSAxLCBpbWRiX3lfdGVzdCA9PSAwKSlbMF0KCiMgV2UgdGFrZSBvbmUgdHJ1ZSBwb3NpdGl2ZSBhbmQgb25lIGZhbHNlIHBvc2l0aXZlIGV4YW1wbGUgdG8gZGVtbyBleHBsYW5hdGlvbi4KaW1kYl9yZl90cF9leHAgPSBpbWRiX3JmX2V4cGxhaW5lci5leHBsYWluX2luc3RhbmNlKAogIGltZGJfcmV2aWV3c190ZXN0W2ltZGJfcmZfdHBfaWR4WzBdXSwgaW1kYl9yZl9waXBlLnByZWRpY3RfcHJvYmEsIG51bV9mZWF0dXJlcz02KQppbWRiX3JmX2ZwX2V4cCA9IGltZGJfcmZfZXhwbGFpbmVyLmV4cGxhaW5faW5zdGFuY2UoCiAgaW1kYl9yZXZpZXdzX3Rlc3RbaW1kYl9yZl9mcF9pZHhbMF1dLCBpbWRiX3JmX3BpcGUucHJlZGljdF9wcm9iYSwgbnVtX2ZlYXR1cmVzPTYpCiMgRm9yIGlweW5iLCBvbmUgY2FuIHNpbXBseSBjYWxsIGltZGJfdHBfZXhwLnNob3dfaW5fbm90ZWJvb2sodGV4dD1UcnVlKSB0byBlbWJlZCB0aGUgaHRtbCBvdXRwdXQuCgppbWRiX3JmX3RwX2V4cC5zYXZlX3RvX2ZpbGUoIi90bXAvZXhwbGFpbl90ZXh0X3JmX3RwLmh0bWwiKQppbWRiX3JmX2ZwX2V4cC5zYXZlX3RvX2ZpbGUoIi90bXAvZXhwbGFpbl90ZXh0X3JmX2ZwLmh0bWwiKQpgYGAKCiMjIyMgQSBUcnVlIFBvc2l0aXZlIFByZWRpY3Rpb24gRXhwbGFpbmVkIHstfQoKYGBge3IsIGVjaG89RkFMU0V9CmlmICggIWZpbGUuZXhpc3RzKCJsaW1lLmpzIikgKSB7CiAgd3JpdGVfbGltZV9qcygiL3RtcC9leHBsYWluX3RleHRfcmZfdHAuaHRtbCIpCn0KaHRtbHRvb2xzOjppbmNsdWRlSFRNTChwYXJzZV9saW1lX2h0bWxfb3V0cHV0KCIvdG1wL2V4cGxhaW5fdGV4dF9yZl90cC5odG1sIikpCmBgYAoKIyMjIyBBIEZhbHNlIFBvc2l0aXZlIFByZWRpY3Rpb24gRXhwbGFpbmVkIHstfQoKYGBge3IsIGVjaG89RkFMU0V9Cmh0bWx0b29sczo6aW5jbHVkZUhUTUwocGFyc2VfbGltZV9odG1sX291dHB1dCgiL3RtcC9leHBsYWluX3RleHRfcmZfZnAuaHRtbCIpKQpgYGAKCioqVE9ETzogRGlzY3VzcyB0aGUgcmVzdWx0LioqCgojIyMgRXhwbGFpbiBOZXVyYWwgTmV0cyB3aXRoIFdvcmQgRW1iZWRkaW5ncwoKTm93IGxldCdzIHRyeSBhIG5ldXJhbCBuZXR3b3JrIG1vZGVsIHdpdGggd29yZCBlbWJlZGRpbmdzIHRyYWluZWQgZnJvbSBzY3JhdGNoLgpXZSB1c2UgYHRlbnNvcmZsb3cua2VyYXNgIEFQSSB0byBxdWlja2x5IGJ1aWxkIGFuZCB0cmFpbiBhIG5ldXJhbCBuZXQuCldlIGF2ZXJhZ2Ugd29yZCBlbWJlZGRpbmdzIGFzIHRoZSBkb2N1bWVudCBlbWJlZGRpbmdzIGZvciBlYWNoIHJldmlldywKdGhlbiBmZWVkLWZvcndhcmQgYSBSZUxVIGxheWVyIGJlZm9yZSB0aGUgc2lnbW9pZCBhY3RpdmF0aW9uIGZvciBjcm9zcy1lbnRyb3B5IG9wdGltaXphdGlvbi4KCkFzIGFuIGV4ZXJjaXNlLAppbnN0ZWFkIG9mIHJlLXVzaW5nIHRoZSB2b2NhYnVsYXJ5IGJ1aWx0IGJ5IGBUZmlkZlZlY3Rvcml6ZXJgIHdpdGggYHNjaWtpdC1sZWFybmAsCndlIHdpbGwgcmUtdG9rZW5pemUgdGhlIHRleHQgZGF0YSB3aXRoIGBrZXJhcy5wcmVwcm9jZXNzaW5nYCBtb2R1bGUuClRoZSBpbmhlcmVudCBjb25zaXN0ZW5jeSB1bmRlciB0aGUgS2VyYXMgZnJhbWV3b3JrIHdpbGwgYWxzbyBzaW1wbGlmeSBvdXIgbGF0dGVyIHdvcmtzIG9uIG5ldHdvcmsgbGF5ZXJpbmcuCgpgYGB7cHl0aG9uIGltZGJfbm59CmZyb20gdGVuc29yZmxvdy5rZXJhcy5wcmVwcm9jZXNzaW5nLnRleHQgaW1wb3J0IFRva2VuaXplcgpmcm9tIHRlbnNvcmZsb3cua2VyYXMucHJlcHJvY2Vzc2luZy5zZXF1ZW5jZSBpbXBvcnQgcGFkX3NlcXVlbmNlcwoKIyBCdWlsZCB2b2NhYnVsYXJ5LiBXZSB1c2Ugc2ltaWxhciBzaXplIGFzIGluIG91ciBwcmV2aW91cyBUZmlkZlZlY3Rvcml6ZXIuCiMgU2luY2Ugd2Ugd2lsbCB1c2UgemVybyBwYWRkaW5nLCAwIGNhbm5vdCBiZSB1c2VkIGFzIE9PViBpbmRleC4KIyBLZXJhcyB0b2tlbml6ZXIgYnkgZGVmYXVsdCByZXNlcnZlcyAwIGFscmVhZHkuIE9PViB0b2tlbiwgaWYgdXNlZCwgd2lsbCBiZSBpbmRleGVkIGF0IDEuCiMgTm90ZSB0aGF0IGxlbih0b2tlbml6ZXIuaW5kZXhfd29yZCkgd2lsbCBiZSBhbGwgdm9jYWJ1bGFyeSBpbnN0ZWFkIG9mIGBudW1fd29yZHNgLgp2b2NhYl9zaXplID0gMjAwMDEgICMgKzEgZm9yIDAgaW5kZXggdXNlZCBmb3IgcGFkZGluZy4Kb292X3Rva2VuID0gIjx1bms+Igp0b2tlbml6ZXIgPSBUb2tlbml6ZXIobG93ZXI9VHJ1ZSwgb292X3Rva2VuPW9vdl90b2tlbiwgbnVtX3dvcmRzPXZvY2FiX3NpemUpCnRva2VuaXplci5maXRfb25fdGV4dHMoaW1kYl9yZXZpZXdzX3RyYWluKQoKIyBFbmNvZGUgdGV4dCB3aXRoIHBhZGRpbmcgdG8gZW5zdXJlIGZpeGVkLWxlbmd0aCBpbnB1dC4Kc2VxX3RyYWluID0gdG9rZW5pemVyLnRleHRzX3RvX3NlcXVlbmNlcyhpbWRiX3Jldmlld3NfdHJhaW4pCnNlcV90cmFpbl9wYWRkZWQgPSBwYWRfc2VxdWVuY2VzKHNlcV90cmFpbiwgcGFkZGluZz0icG9zdCIpCm1heGxlbiA9IHNlcV90cmFpbl9wYWRkZWQuc2hhcGVbMV0Kc2VxX3Rlc3QgPSB0b2tlbml6ZXIudGV4dHNfdG9fc2VxdWVuY2VzKGltZGJfcmV2aWV3c190ZXN0KQpzZXFfdGVzdF9wYWRkZWQgPSBwYWRfc2VxdWVuY2VzKHNlcV90ZXN0LCBwYWRkaW5nPSJwb3N0IiwgbWF4bGVuPW1heGxlbikKCmFzc2VydCB0b2tlbml6ZXIuaW5kZXhfd29yZFsxXSA9PSBvb3ZfdG9rZW4KYXNzZXJ0IHNlcV90cmFpbl9wYWRkZWQubWF4KCkgPT0gdm9jYWJfc2l6ZSAtIDEKCiMgV3JhcCBLZXJhcyBTZXF1ZW50aWFsIG1vZGVsIHdpdGggc2Npa2l0LWxlYXJuIEFQSS4KIyBUaGlzIGlzIGJlY2F1c2UgTGltZVRleHRFeHBsYWluZXIgc2VlbXMgYnVnZ3kgd2l0aCBhIG5hdGl2ZSBLZXJhcyBtb2RlbC4Kbm5fbW9kZWxfZmlsZSA9ICJtb2RlbHMvdGV4dF9jbGZfbm4uaDUiCgpkZWYgbm5fbW9kZWxfZm4oKToKICBlbWJlZGRpbmdfc2l6ZSA9IDY0CiAgbW9kZWwgPSB0Zi5rZXJhcy5TZXF1ZW50aWFsKFsKICAgIHRmLmtlcmFzLmxheWVycy5FbWJlZGRpbmcoCiAgICAgIHZvY2FiX3NpemUsIGVtYmVkZGluZ19zaXplLCBpbnB1dF9sZW5ndGg9bWF4bGVuLAogICAgICBtYXNrX3plcm89VHJ1ZSwgbmFtZT0id29yZF9lbWJlZGRpbmciKSwKICAgIHRmLmtlcmFzLmxheWVycy5HbG9iYWxBdmVyYWdlUG9vbGluZzFEKG5hbWU9ImRvY19lbWJlZGRpbmciKSwKICAgIHRmLmtlcmFzLmxheWVycy5EZW5zZShlbWJlZGRpbmdfc2l6ZSAvIDIsIGFjdGl2YXRpb249InJlbHUiLCBuYW1lPSJyZWx1IiksCiAgICB0Zi5rZXJhcy5sYXllcnMuRGVuc2UoMSwgYWN0aXZhdGlvbj0ic2lnbW9pZCIsIG5hbWU9InNpZ21vaWQiKQogIF0sIG5hbWU9Im5uX2NsYXNzaWZpZXIiKQogIG1vZGVsLmNvbXBpbGUob3B0aW1pemVyPSJhZGFtIiwKICAgICAgICAgICAgICAgIGxvc3M9ImJpbmFyeV9jcm9zc2VudHJvcHkiLAogICAgICAgICAgICAgICAgbWV0cmljcz1bImFjY3VyYWN5Il0pCiAgcmV0dXJuIG1vZGVsCgpwcmludChubl9tb2RlbF9mbigpLnN1bW1hcnkobGluZV9sZW5ndGg9OTApKQoKaW1kYl9ubiA9IHRmLmtlcmFzLndyYXBwZXJzLnNjaWtpdF9sZWFybi5LZXJhc0NsYXNzaWZpZXIobm5fbW9kZWxfZm4pCmlmIG9zLnBhdGguZXhpc3RzKG5uX21vZGVsX2ZpbGUpOgogICMgUmVzdG9yZSB0aGUgbW9kZWwgd2l0aCB3cmFwcGVyLgogIGltZGJfbm4ubW9kZWwgPSB0Zi5rZXJhcy5tb2RlbHMubG9hZF9tb2RlbChubl9tb2RlbF9maWxlKQogIGltZGJfbm4uY2xhc3Nlc18gPSBucC5hcnJheShbMCwgMV0pCmVsc2U6CiAgbWV0cmljcyA9IGltZGJfbm4uZml0KAogICAgeD1zZXFfdHJhaW5fcGFkZGVkLCB5PWltZGJfeV90cmFpbiwKICAgIGJhdGNoX3NpemU9MjU2LCBlcG9jaHM9MTAsCiAgICB2YWxpZGF0aW9uX2RhdGE9KHNlcV90ZXN0X3BhZGRlZCwgaW1kYl95X3Rlc3QpLAogICAgdmFsaWRhdGlvbl9zdGVwcz0yMCwKICAgIGNhbGxiYWNrcz1bCiAgICAgIHRmLmtlcmFzLmNhbGxiYWNrcy5FYXJseVN0b3BwaW5nKG1vbml0b3I9InZhbF9sb3NzIiwgcGF0aWVuY2U9MiksCiAgICAgIHRmLmtlcmFzLmNhbGxiYWNrcy5Nb2RlbENoZWNrcG9pbnQobm5fbW9kZWxfZmlsZSwgbW9uaXRvcj0idmFsX2xvc3MiLCBzYXZlX2Jlc3Rfb25seT1UcnVlKQogICAgXSwKICAgIHZlcmJvc2U9MikKCmltZGJfbm5feWhhdCA9IG5wLnNxdWVlemUoaW1kYl9ubi5wcmVkaWN0KHNlcV90ZXN0X3BhZGRlZCkpCmltZGJfbm5fcHJlZCA9IChpbWRiX25uX3loYXQgPiAuNSkuYXN0eXBlKGludCkKCnByaW50KGNsYXNzaWZpY2F0aW9uX3JlcG9ydChpbWRiX3lfdGVzdCwgaW1kYl9ubl9wcmVkKSkKcHJpbnQocm9jX2F1Y19zY29yZShpbWRiX3lfdGVzdCwgaW1kYl9ubl9wcmVkKSkKYGBgCgpgYGB7cHl0aG9uIGxpbWVfaW1kYl9ubn0KZGVmIG5uX3ByZWRpY3RfZm4odGV4dCk6CiAgIyBUaGlzIGlzIGZvciBza2xlYXJuIHdyYXBwZXIgb25seS4KICBzZXEgPSB0b2tlbml6ZXIudGV4dHNfdG9fc2VxdWVuY2VzKHRleHQpCiAgc2VxID0gcGFkX3NlcXVlbmNlcyhzZXEsIHBhZGRpbmc9InBvc3QiLCBtYXhsZW49bWF4bGVuKQogIHJldHVybiBpbWRiX25uLnByZWRpY3RfcHJvYmEoc2VxKQoKaW1kYl9ubl9leHBsYWluZXIgPSBMaW1lVGV4dEV4cGxhaW5lcihjbGFzc19uYW1lcz1bIk5lZ2F0aXZlIiwgIlBvc2l0aXZlIl0pCgojIEV4cGxhaW4gdGhlIHNhbWUgZXhhbXBsZXMgYXMgaW4gUkYuCmltZGJfbm5fdHBfZXhwID0gaW1kYl9ubl9leHBsYWluZXIuZXhwbGFpbl9pbnN0YW5jZSgKICBpbWRiX3Jldmlld3NfdGVzdFtpbWRiX3JmX3RwX2lkeFswXV0sIG5uX3ByZWRpY3RfZm4sIG51bV9mZWF0dXJlcz02KQppbWRiX25uX2ZwX2V4cCA9IGltZGJfbm5fZXhwbGFpbmVyLmV4cGxhaW5faW5zdGFuY2UoCiAgaW1kYl9yZXZpZXdzX3Rlc3RbaW1kYl9yZl9mcF9pZHhbMF1dLCBubl9wcmVkaWN0X2ZuLCBudW1fZmVhdHVyZXM9NikKCmltZGJfbm5fdHBfZXhwLnNhdmVfdG9fZmlsZSgiL3RtcC9leHBsYWluX3RleHRfbm5fdHAuaHRtbCIpCmltZGJfbm5fZnBfZXhwLnNhdmVfdG9fZmlsZSgiL3RtcC9leHBsYWluX3RleHRfbm5fZnAuaHRtbCIpCmBgYAoKYGBge3IsIGVjaG89RkFMU0V9Cmh0bWx0b29sczo6aW5jbHVkZUhUTUwocGFyc2VfbGltZV9odG1sX291dHB1dCgiL3RtcC9leHBsYWluX3RleHRfbm5fdHAuaHRtbCIpKQpgYGAKCmBgYHtyLCBlY2hvPUZBTFNFfQpodG1sdG9vbHM6OmluY2x1ZGVIVE1MKHBhcnNlX2xpbWVfaHRtbF9vdXRwdXQoIi90bXAvZXhwbGFpbl90ZXh0X25uX2ZwLmh0bWwiKSkKYGBgCgoqKlRPRE86IERpc2N1c3MgdGhlIGRpZmZlcmVuY2UgYmV0d2VlbiBSRiBhbmQgTk4uKioKCiMjIyBFeHBsYWluIFRyYW5zZmVyIExlYXJuaW5nCgpPbmUgc3RlcCBmdXJ0aGVyLApsZXQncyB1c2UgcHJlLXRyYWluZWQgd29yZCBlbWJlZGRpbmdzIGZvciB0aGUgbmV1cmFsIG5ldHMgYW5kIGJ1aWxkIGFub3RoZXIgZXhwbGFuYXRpb24gbW9kZWwuCldlIHdpbGwgdXNlIFtHbG9WZV0oaHR0cHM6Ly9ubHAuc3RhbmZvcmQuZWR1L3Byb2plY3RzL2dsb3ZlLykgKEBwZW5uaW5ndG9uMjAxNGdsb3ZlKS4KV2UgdXNlIGp1c3QgdGhlIHNtYWxsZXIgR2xvVmUgbW9kZWwgc2luY2Ugb3VyIGRhdGFzZXQgaXMgcXVpdGUgc21hbGwuCkluIGJ1aWxkaW5nIHRoZSBHbG9WZSBlbWJlZGRpbmdzIHdlIG5lZWQgdG8gdGFrZSBzcGVjaWFsIGNhcmUgYWJvdXQgb3V0LW9mLXZvY2FidWxhcnkgdG9rZW4gQU5EIHBhZGRpbmcgaW5kZXggc2luY2Ugd2Ugd2lsbCBiZSB1c2luZyB0aGUgS2VyYXMgQVBJLgoKYGBge3B5dGhvbiBtYXliZV9kb3dubG9hZF9nbG92ZSwgcmVzdWx0cz0iaGlkZSJ9CiMgRG93bmxvYWQgR2xvVmUgcHJlLXRyYWluZWQgZW1iZWRkaW5ncy4KIyBUaGUgZmlsZSBpcyBhYm91dCA4MDBNQiBzbyBtYXkgdGFrZSBzb21lIHRpbWUuCmhvbWUgPSBvcy5wYXRoLmV4cGFuZHVzZXIoIn4iKQpjYWNoZV9kaXIgPSBvcy5wYXRoLmpvaW4oaG9tZSwgIi5rZXJhcyIpCmdsb3ZlNmJfcmVtb3RlX3BhdGggPSAiaHR0cDovL25scC5zdGFuZm9yZC5lZHUvZGF0YS9nbG92ZS42Qi56aXAiCmdsb3ZlNmJfbG9jYWxfcGF0aCA9IG9zLnBhdGguam9pbihjYWNoZV9kaXIsICJkYXRhc2V0cyIsICJnbG92ZS42Qi41MGQudHh0IikKZ2xvdmU2Yl9mbmFtZSA9IG9zLnBhdGguYmFzZW5hbWUoZ2xvdmU2Yl9yZW1vdGVfcGF0aCkKaWYgbm90IG9zLnBhdGguZXhpc3RzKGdsb3ZlNmJfbG9jYWxfcGF0aCk6CiAgXyA9IHRmLmtlcmFzLnV0aWxzLmdldF9maWxlKGZuYW1lPWdsb3ZlNmJfZm5hbWUsIG9yaWdpbj1nbG92ZTZiX3JlbW90ZV9wYXRoLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICBleHRyYWN0PVRydWUsIGNhY2hlX2Rpcj1jYWNoZV9kaXIpCgpnbG92ZV9hbGwgPSBwZC5yZWFkX2NzdihnbG92ZTZiX2xvY2FsX3BhdGgsIHNlcD0iICIsIGhlYWRlcj1Ob25lLCBpbmRleF9jb2w9MCwgcXVvdGluZz0zKQpgYGAKCmBgYHtweXRob24gaW1kYl90cmFuc2Zlcl9sZWFybmluZ192b2NhYn0KIyBNYXAgdm9jYWJ1bGFyeSB0byBwcmUtdHJhaW5lZCBlbWJlZGRpbmdzLgptYXRjaGVkX3Rva3MgPSBbXQpmb3IgaSwgdyBpbiB0b2tlbml6ZXIuaW5kZXhfd29yZC5pdGVtcygpOgogIGlmIGkgPCB2b2NhYl9zaXplOgogICAgaWYgdyBpbiBnbG92ZV9hbGwuaW5kZXg6CiAgICAgIG1hdGNoZWRfdG9rcy5hcHBlbmQodykKICAgIGVsc2U6CiAgICAgIG1hdGNoZWRfdG9rcy5hcHBlbmQob292X3Rva2VuKQoKIyBOb3RlIHRoYXQgR2xvVmUgcHJlLXRyYWluZWQgZW1iZWRkaW5ncyBkb2VzIG5vdCBpbmNsdWRlIGl0cyBvd24gT09WIHRva2VuLgojIFdlIHdpbGwgdXNlIGEgZ2xvYmFsIGF2ZXJhZ2UgZW1iZWRkaW5nIHRvIHJlcHJlc2VudCBPT1YgdG9rZW4uCnByaW50KGxlbihbdCBmb3IgdCBpbiBtYXRjaGVkX3Rva3MgaWYgdCA9PSBvb3ZfdG9rZW5dKSkgICMgSG93IG1hbnkgT09Wcz8KCmdsb3ZlX2FsbC5sb2Nbb292X3Rva2VuXSA9IGdsb3ZlX2FsbC52YWx1ZXMubWVhbihheGlzPTApCmdsb3ZlID0gZ2xvdmVfYWxsLmxvY1ttYXRjaGVkX3Rva3NdLnZhbHVlcwoKIyBBcHBlbmQgZHVtbXkgMC1pbmRleCB2ZWN0b3IgdG8gc3VwcG9ydCBwYWRkaW5nLgpnbG92ZSA9IG5wLnZzdGFjayhbbnAuemVyb3MoKDEsIGdsb3ZlLnNoYXBlWzFdKSksIGdsb3ZlXSkKcHJpbnQoZ2xvdmUuc2hhcGUpCmBgYAoKTm93IGxldCdzIGJ1aWxkIHRoZSBuZXVyYWwgbmV0d29yay4KTW9zdCBvZiB0aGUgY29kZSB3aWxsIGJlIHRoZSBzYW1lIGFzIGJlZm9yZSwKb25seSB0aGUgYEVtYmVkZGluZ2AgbGF5ZXIgbm93IHdlIHdpbGwgdXNlIGEgY29uc3RhbnQgbWF0cml4IGZvciBpbml0aWFsaXphdGlvbi4KV2UgbWFrZSB0aGUgR2xvVmUgZW1iZWRkaW5ncyAqdHJhaW5hYmxlKiBzbyBpdCB3aWxsIGZ1cnRoZXIgYWRhcHQgdG8gb3VyIHNwZWNpZmljIGRhdGFzZXQuCgpgYGB7cHl0aG9uIGltZGJfdHJhbnNmZXJfbGVhcm5pbmd9CnRyX21vZGVsX2ZpbGUgPSAibW9kZWxzL3RleHRfY2xmX3RyLmg1IgoKZGVmIHRyX21vZGVsX2ZuKCk6CiAgZW1iZWRkaW5nX3NpemUgPSBnbG92ZS5zaGFwZVsxXQogIG1vZGVsID0gdGYua2VyYXMuU2VxdWVudGlhbChbCiAgICB0Zi5rZXJhcy5sYXllcnMuRW1iZWRkaW5nKAogICAgICB2b2NhYl9zaXplLCBlbWJlZGRpbmdfc2l6ZSwgaW5wdXRfbGVuZ3RoPW1heGxlbiwKICAgICAgZW1iZWRkaW5nc19pbml0aWFsaXplcj10Zi5rZXJhcy5pbml0aWFsaXplcnMuQ29uc3RhbnQoZ2xvdmUpLAogICAgICB0cmFpbmFibGU9VHJ1ZSwgbWFza196ZXJvPVRydWUsIG5hbWU9Imdsb3ZlX2VtYmVkZGluZyIpLAogICAgdGYua2VyYXMubGF5ZXJzLkdsb2JhbEF2ZXJhZ2VQb29saW5nMUQobmFtZT0iZG9jX2VtYmVkZGluZyIpLAogICAgdGYua2VyYXMubGF5ZXJzLkRlbnNlKGVtYmVkZGluZ19zaXplIC8gMiwgYWN0aXZhdGlvbj0icmVsdSIsIG5hbWU9InJlbHUiKSwKICAgIHRmLmtlcmFzLmxheWVycy5EZW5zZSgxLCBhY3RpdmF0aW9uPSJzaWdtb2lkIiwgbmFtZT0ic2lnbW9pZCIpCiAgXSwgbmFtZT0idHJfY2xhc3NpZmllciIpCiAgbW9kZWwuY29tcGlsZShvcHRpbWl6ZXI9ImFkYW0iLAogICAgICAgICAgICAgICAgbG9zcz0iYmluYXJ5X2Nyb3NzZW50cm9weSIsCiAgICAgICAgICAgICAgICBtZXRyaWNzPVsiYWNjdXJhY3kiXSkKICByZXR1cm4gbW9kZWwKCnByaW50KHRyX21vZGVsX2ZuKCkuc3VtbWFyeShsaW5lX2xlbmd0aD05MCkpCgppbWRiX3RyID0gdGYua2VyYXMud3JhcHBlcnMuc2Npa2l0X2xlYXJuLktlcmFzQ2xhc3NpZmllcih0cl9tb2RlbF9mbikKaWYgb3MucGF0aC5leGlzdHModHJfbW9kZWxfZmlsZSk6CiAgIyBSZXN0b3JlIHRoZSBtb2RlbCB3aXRoIHdyYXBwZXIuCiAgaW1kYl90ci5tb2RlbCA9IHRmLmtlcmFzLm1vZGVscy5sb2FkX21vZGVsKHRyX21vZGVsX2ZpbGUpCiAgaW1kYl90ci5jbGFzc2VzXyA9IG5wLmFycmF5KFswLCAxXSkKZWxzZToKICBpbWRiX3RyID0gdGYua2VyYXMud3JhcHBlcnMuc2Npa2l0X2xlYXJuLktlcmFzQ2xhc3NpZmllcih0cl9tb2RlbF9mbikKICBtZXRyaWNzID0gaW1kYl90ci5maXQoCiAgICB4PXNlcV90cmFpbl9wYWRkZWQsIHk9aW1kYl95X3RyYWluLAogICAgYmF0Y2hfc2l6ZT0yNTYsIGVwb2Nocz0yMCwKICAgIHZhbGlkYXRpb25fZGF0YT0oc2VxX3Rlc3RfcGFkZGVkLCBpbWRiX3lfdGVzdCksCiAgICB2YWxpZGF0aW9uX3N0ZXBzPTIwLAogICAgY2FsbGJhY2tzPVsKICAgICAgdGYua2VyYXMuY2FsbGJhY2tzLkVhcmx5U3RvcHBpbmcobW9uaXRvcj0idmFsX2xvc3MiLCBwYXRpZW5jZT0yKSwKICAgICAgdGYua2VyYXMuY2FsbGJhY2tzLk1vZGVsQ2hlY2twb2ludCh0cl9tb2RlbF9maWxlLCBtb25pdG9yPSJ2YWxfbG9zcyIsIHNhdmVfYmVzdF9vbmx5PVRydWUpCiAgICBdLAogICAgdmVyYm9zZT0yKQoKaW1kYl90cl95aGF0ID0gbnAuc3F1ZWV6ZShpbWRiX3RyLnByZWRpY3Qoc2VxX3Rlc3RfcGFkZGVkKSkKaW1kYl90cl9wcmVkID0gKGltZGJfdHJfeWhhdCA+IC41KS5hc3R5cGUoaW50KQoKcHJpbnQoY2xhc3NpZmljYXRpb25fcmVwb3J0KGltZGJfeV90ZXN0LCBpbWRiX3RyX3ByZWQpKQpwcmludChyb2NfYXVjX3Njb3JlKGltZGJfeV90ZXN0LCBpbWRiX3RyX3loYXQpKQpgYGAKCmBgYHtweXRob24gbGltZV9pbWRiX3RyYW5zZmVyX2xlYXJuaW5nfQpkZWYgdHJfcHJlZGljdF9mbih0ZXh0KToKICAjIFRoaXMgaXMgZm9yIHNrbGVhcm4gd3JhcHBlciBvbmx5LgogIHNlcSA9IHRva2VuaXplci50ZXh0c190b19zZXF1ZW5jZXModGV4dCkKICBzZXEgPSBwYWRfc2VxdWVuY2VzKHNlcSwgcGFkZGluZz0icG9zdCIsIG1heGxlbj1tYXhsZW4pCiAgcmV0dXJuIGltZGJfdHIucHJlZGljdF9wcm9iYShzZXEpCgppbWRiX3RyX2V4cGxhaW5lciA9IExpbWVUZXh0RXhwbGFpbmVyKGNsYXNzX25hbWVzPVsiTmVnYXRpdmUiLCAiUG9zaXRpdmUiXSkKCiMgRXhwbGFpbiB0aGUgc2FtZSBleGFtcGxlcyBhcyBpbiBSRi4KaW1kYl90cl90cF9leHAgPSBpbWRiX3RyX2V4cGxhaW5lci5leHBsYWluX2luc3RhbmNlKAogIGltZGJfcmV2aWV3c190ZXN0W2ltZGJfcmZfdHBfaWR4WzBdXSwgdHJfcHJlZGljdF9mbiwgbnVtX2ZlYXR1cmVzPTYpCmltZGJfdHJfZnBfZXhwID0gaW1kYl90cl9leHBsYWluZXIuZXhwbGFpbl9pbnN0YW5jZSgKICBpbWRiX3Jldmlld3NfdGVzdFtpbWRiX3JmX2ZwX2lkeFswXV0sIHRyX3ByZWRpY3RfZm4sIG51bV9mZWF0dXJlcz02KQoKaW1kYl90cl90cF9leHAuc2F2ZV90b19maWxlKCIvdG1wL2V4cGxhaW5fdGV4dF90cl90cC5odG1sIikKaW1kYl90cl9mcF9leHAuc2F2ZV90b19maWxlKCIvdG1wL2V4cGxhaW5fdGV4dF90cl9mcC5odG1sIikKYGBgCgpgYGB7ciwgZWNobz1GQUxTRX0KaHRtbHRvb2xzOjppbmNsdWRlSFRNTChwYXJzZV9saW1lX2h0bWxfb3V0cHV0KCIvdG1wL2V4cGxhaW5fdGV4dF90cl90cC5odG1sIikpCmBgYAoKYGBge3IsIGVjaG89RkFMU0V9Cmh0bWx0b29sczo6aW5jbHVkZUhUTUwocGFyc2VfbGltZV9odG1sX291dHB1dCgiL3RtcC9leHBsYWluX3RleHRfdHJfZnAuaHRtbCIpKQpgYGAKCioqVE9ETzogRGlzY3Vzc2lvbi4qKgoKIyMjIEV4cGxhaW4gUmVjdXJyZW50IE5ldXJhbCBOZXRzCgpBcyBhIGZpbmFsIGV4ZXJjaXNlIG9uIHRleHQgY2xhc3NpZmljYXRpb24sCmxldCdzIGV4cGVyaW1lbnQgdGhlIGV4cGxhbmF0aW9uIG1vZGVsIHdpdGggYSByZWN1cnJlbnQgbmV1cmFsIG5ldHdvcmsgKFJOTikuCk5vdGUgdGhhdCwgZXZlbiBmb3IgYSBzaW5nbGUgbGF5ZXIsIHRoaXMgd2lsbCBiZSBwcm9oaWJpdGl2ZWx5IHNsb3cgd2l0aG91dCBhIEdQVS4KCmBgYHtweXRob24gaW1kYl9ybm59CnJubl9tb2RlbF9maWxlID0gIm1vZGVscy90ZXh0X2NsZl9ybm4uaDUiCgpkZWYgcm5uX21vZGVsX2ZuKCk6CiAgZW1iZWRkaW5nX3NpemUgPSA2NAogIG1vZGVsID0gdGYua2VyYXMuU2VxdWVudGlhbChbCiAgICB0Zi5rZXJhcy5sYXllcnMuRW1iZWRkaW5nKAogICAgICB2b2NhYl9zaXplLCBlbWJlZGRpbmdfc2l6ZSwKICAgICAgaW5wdXRfbGVuZ3RoPW1heGxlbiwgbWFza196ZXJvPVRydWUsIG5hbWU9IndvcmRfZW1iZWRkaW5nIiksCiAgICB0Zi5rZXJhcy5sYXllcnMuR1JVKDY0LCBkcm9wb3V0PS4yLCBuYW1lPSJHUlUiKSwKICAgIHRmLmtlcmFzLmxheWVycy5EZW5zZSgxLCBhY3RpdmF0aW9uPSJzaWdtb2lkIiwgbmFtZT0ic2lnbW9pZCIpCiAgXSwgbmFtZT0icm5uX2NsYXNzaWZpZXIiKQogIG1vZGVsLmNvbXBpbGUob3B0aW1pemVyPSJhZGFtIiwKICAgICAgICAgICAgICAgIGxvc3M9ImJpbmFyeV9jcm9zc2VudHJvcHkiLAogICAgICAgICAgICAgICAgbWV0cmljcz1bImFjY3VyYWN5Il0pCiAgcmV0dXJuIG1vZGVsCgpwcmludChybm5fbW9kZWxfZm4oKS5zdW1tYXJ5KGxpbmVfbGVuZ3RoPTkwKSkKCmltZGJfcm5uID0gdGYua2VyYXMud3JhcHBlcnMuc2Npa2l0X2xlYXJuLktlcmFzQ2xhc3NpZmllcihybm5fbW9kZWxfZm4pCmlmIG9zLnBhdGguZXhpc3RzKHJubl9tb2RlbF9maWxlKToKICAjICAjIFJlc3RvcmUgdGhlIG1vZGVsIHdpdGggd3JhcHBlci4KICBpbWRiX3Jubi5tb2RlbCA9IHRmLmtlcmFzLm1vZGVscy5sb2FkX21vZGVsKHJubl9tb2RlbF9maWxlKQogIGltZGJfcm5uLmNsYXNzZXNfID0gbnAuYXJyYXkoWzAsIDFdKQplbHNlOgogIG1ldHJpY3MgPSBpbWRiX3Jubi5maXQoCiAgICB4PXNlcV90cmFpbl9wYWRkZWQsIHk9aW1kYl95X3RyYWluLAogICAgYmF0Y2hfc2l6ZT0zMiwgZXBvY2hzPTEwLAogICAgdmFsaWRhdGlvbl9kYXRhPShzZXFfdGVzdF9wYWRkZWQsIGltZGJfeV90ZXN0KSwKICAgIHZhbGlkYXRpb25fc3RlcHM9MjAsCiAgICBjYWxsYmFja3M9WwogICAgICB0Zi5rZXJhcy5jYWxsYmFja3MuRWFybHlTdG9wcGluZyhtb25pdG9yPSJ2YWxfbG9zcyIsIHBhdGllbmNlPTIpLAogICAgICB0Zi5rZXJhcy5jYWxsYmFja3MuTW9kZWxDaGVja3BvaW50KHJubl9tb2RlbF9maWxlLCBtb25pdG9yPSJ2YWxfbG9zcyIsIHNhdmVfYmVzdF9vbmx5PVRydWUpCiAgICBdLAogICAgdmVyYm9zZT0yKQoKaW1kYl9ybm5feWhhdCA9IG5wLnNxdWVlemUoaW1kYl9ybm4ucHJlZGljdChzZXFfdGVzdF9wYWRkZWQpKQppbWRiX3Jubl9wcmVkID0gKGltZGJfcm5uX3loYXQgPiAuNSkuYXN0eXBlKGludCkKCnByaW50KGNsYXNzaWZpY2F0aW9uX3JlcG9ydChpbWRiX3lfdGVzdCwgaW1kYl9ybm5fcHJlZCkpCnByaW50KHJvY19hdWNfc2NvcmUoaW1kYl95X3Rlc3QsIGltZGJfcm5uX3loYXQpKQpgYGAKClNpbmNlIHRoZSBkYXRhc2V0IGlzIHJhdGhlciBzbWFsbCwKd2UgZGlkbid0IHNlZSBhbnkgYWR2YW50YWdlIG9mIFJOTiBvdmVyIGEgc2ltcGxlIHBvb2xpbmcgZW1iZWRkaW5nIG1vZGVsLgpUaGF0J3Mgc2VlIGhvdyB0aGUgZXhwbGFuYXRpb24gY2FuIGRpZmZlciwgYWdhaW4sIGZvciB0aGUgc2FtZSB0d28gZXhhbXBsZXM6CgpgYGB7cHl0aG9uIGxpbWVfaW1kYl9ybm59CmRlZiBybm5fcHJlZGljdF9mbih0ZXh0KToKICAjIFRoaXMgaXMgZm9yIHNrbGVhcm4gd3JhcHBlciBvbmx5LgogIHNlcSA9IHRva2VuaXplci50ZXh0c190b19zZXF1ZW5jZXModGV4dCkKICBzZXEgPSBwYWRfc2VxdWVuY2VzKHNlcSwgcGFkZGluZz0icG9zdCIsIG1heGxlbj1tYXhsZW4pCiAgcmV0dXJuIGltZGJfcm5uLnByZWRpY3RfcHJvYmEoc2VxKQoKaW1kYl9ybm5fZXhwbGFpbmVyID0gTGltZVRleHRFeHBsYWluZXIoY2xhc3NfbmFtZXM9WyJOZWdhdGl2ZSIsICJQb3NpdGl2ZSJdKQoKIyBFeHBsYWluIHRoZSBzYW1lIGV4YW1wbGVzIGFzIGluIFJGLgppbWRiX3Jubl90cF9leHAgPSBpbWRiX3Jubl9leHBsYWluZXIuZXhwbGFpbl9pbnN0YW5jZSgKICBpbWRiX3Jldmlld3NfdGVzdFtpbWRiX3JmX3RwX2lkeFswXV0sIHJubl9wcmVkaWN0X2ZuLCBudW1fZmVhdHVyZXM9NikKaW1kYl9ybm5fZnBfZXhwID0gaW1kYl9ybm5fZXhwbGFpbmVyLmV4cGxhaW5faW5zdGFuY2UoCiAgaW1kYl9yZXZpZXdzX3Rlc3RbaW1kYl9yZl9mcF9pZHhbMF1dLCBybm5fcHJlZGljdF9mbiwgbnVtX2ZlYXR1cmVzPTYpCgppbWRiX3Jubl90cF9leHAuc2F2ZV90b19maWxlKCIvdG1wL2V4cGxhaW5fdGV4dF9ybm5fdHAuaHRtbCIpCmltZGJfcm5uX2ZwX2V4cC5zYXZlX3RvX2ZpbGUoIi90bXAvZXhwbGFpbl90ZXh0X3Jubl9mcC5odG1sIikKYGBgCgpgYGB7ciwgZWNobz1GQUxTRX0KaHRtbHRvb2xzOjppbmNsdWRlSFRNTChwYXJzZV9saW1lX2h0bWxfb3V0cHV0KCIvdG1wL2V4cGxhaW5fdGV4dF9ybm5fdHAuaHRtbCIpKQpgYGAKCmBgYHtyLCBlY2hvPUZBTFNFfQpodG1sdG9vbHM6OmluY2x1ZGVIVE1MKHBhcnNlX2xpbWVfaHRtbF9vdXRwdXQoIi90bXAvZXhwbGFpbl90ZXh0X3Jubl9mcC5odG1sIikpCmBgYAoKKipUT0RPOiBTdW1tYXJpemUgYWxsIHRleHQgbW9kZWxzLioqCgojIyBPbiBUYWJ1bGFyIERhdGEgQ2xhc3NpZmllcgoKTG90cyBvZiBkYXRhIGNhbiBiZSByZXByZXNlbnRlZCBpbiB0YWJ1bGFyIGZvcm1hdC4KSGVyZSB3ZSB3aWxsIHVzZSBbVUNJIEhlYXJ0IERpc2Vhc2UgZGF0YXNldF0oaHR0cHM6Ly9hcmNoaXZlLmljcy51Y2kuZWR1L21sL2RhdGFzZXRzL0hlYXJ0K0Rpc2Vhc2UpIGZvciBkZW1vLgpQYXJ0aWN1bGFybHksCndlIHVzZSB0aGUgQ2xldmVsYW5kIGRhdGFzZXQgd2hpY2ggaXMgY29tbW9ubHkgdXNlZCBpbiBtYWNoaW5lIGxlYXJuaW5nIHJlc2VhcmNoLl5bVi5BLiBNZWRpY2FsIENlbnRlciwgTG9uZyBCZWFjaCBhbmQgQ2xldmVsYW5kIENsaW5pYyBGb3VuZGF0aW9uOlJvYmVydCBEZXRyYW5vLCBNLkQuLCBQaC5ELl0KCmBgYHtweXRob24gbWF5YmVfZG93bmxvYWRfdWNpaGQsIHJlc3VsdHM9ImhpZGUifQp1Y2loZF9yZW1vdGVfcGF0aCA9ICJodHRwczovL2FyY2hpdmUuaWNzLnVjaS5lZHUvbWwvbWFjaGluZS1sZWFybmluZy1kYXRhYmFzZXMvaGVhcnQtZGlzZWFzZS9wcm9jZXNzZWQuY2xldmVsYW5kLmRhdGEiCnVjaWhkX2ZuYW1lID0gb3MucGF0aC5iYXNlbmFtZSh1Y2loZF9yZW1vdGVfcGF0aCkKdWNpaGRfbG9jYWxfcGF0aCA9IG9zLnBhdGguam9pbihjYWNoZV9kaXIsICJkYXRhc2V0cyIsIHVjaWhkX2ZuYW1lKQoKaWYgbm90IG9zLnBhdGguZXhpc3RzKHVjaWhkX2xvY2FsX3BhdGgpOgogIF8gPSB0Zi5rZXJhcy51dGlscy5nZXRfZmlsZShmbmFtZT11Y2loZF9mbmFtZSwgb3JpZ2luPXVjaWhkX3JlbW90ZV9wYXRoLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICBleHRyYWN0PUZhbHNlLCBjYWNoZV9kaXI9Y2FjaGVfZGlyKQpgYGAKCmBgYHtweXRob24gcHJlcHJvY2Vzc191Y2loZH0KdWNpaGRfYXR0ciA9IFsKICAiYWdlIiwKICAic2V4IiwKICAiY3AiLCAgIyBjaGVzdCBwYWluIHR5cGUgMTogdHlwaWNhbCBhbmdpbmEgMjogYXR5cGljYWwgYW5naW5hIDM6IG5vbi1hbmdpbmFsIHBhaW4gNDogYXN5bXB0b21hdGljCiAgInRyZXN0YnBzIiwgICMgcmVzdGluZyBibG9vZCBwcmVzc3VyZSAoaW4gbW0gSGcgb24gYWRtaXNzaW9uIHRvIHRoZSBob3NwaXRhbCkKICAiY2hvbCIsICAjIHNlcnVtIGNob2xlc3RvcmFsIGluIG1nL2RsCiAgImZicyIsICAjIChmYXN0aW5nIGJsb29kIHN1Z2FyID4gMTIwIG1nL2RsKSAoMSA9IHRydWU7IDAgPSBmYWxzZSkKICAicmVzdGVjZyIsICAjIHJlc3RpbmcgZWxlY3Ryb2NhcmRpb2dyYXBoaWMgcmVzdWx0cyAwOiBub3JtYWwgMTogaGF2aW5nIFNULVQgd2F2ZSBhYm5vcm1hbGl0eSAyOiBzaG93aW5nIHByb2JhYmxlIG9yIGRlZmluaXRlIGxlZnQgdmVudHJpY3VsYXIgaHlwZXJ0cm9waHkgYnkgRXN0ZXMnIGNyaXRlcmlhCiAgInRoYWxhY2giLCAgIyBtYXhpbXVtIGhlYXJ0IHJhdGUgYWNoaWV2ZWQKICAiZXhhbmciLCAgIyBleGVyY2lzZSBpbmR1Y2VkIGFuZ2luYSAoMSA9IHllczsgMCA9IG5vKQogICJvbGRwZWFrIiwgICMgU1QgZGVwcmVzc2lvbiBpbmR1Y2VkIGJ5IGV4ZXJjaXNlIHJlbGF0aXZlIHRvIHJlc3QKICAic2xvcGUiLCAgIyAgdGhlIHNsb3BlIG9mIHRoZSBwZWFrIGV4ZXJjaXNlIFNUIHNlZ21lbnQKICAiY2EiLCAgIyBudW1iZXIgb2YgbWFqb3IgdmVzc2VscyAoMC0zKSBjb2xvcmVkIGJ5IGZsb3Vyb3NvcHkKICAidGhhbCIsICAjIDMgPSBub3JtYWw7IDYgPSBmaXhlZCBkZWZlY3Q7IDcgPSByZXZlcnNhYmxlIGRlZmVjdAogICJsYWJlbCIgICMgZGlhZ25vc2lzIG9mIGhlYXJ0IGRpc2Vhc2UgKGFuZ2lvZ3JhcGhpYyBkaXNlYXNlIHN0YXR1cykgMDogPCA1MCUgZGlhbWV0ZXIgbmFycm93aW5nIDEtNDogPiA1MCUgZGlhbWV0ZXIgbmFycm93aW5nCl0KdWNpaGQgPSBwZC5yZWFkX2Nzdih1Y2loZF9sb2NhbF9wYXRoLCBoZWFkZXI9Tm9uZSwgbmFtZXM9dWNpaGRfYXR0ciwgbmFfdmFsdWVzPSI/IikKY2F0ZWdvcmljYWxfYXR0ciA9IFsiY3AiLCAiZmJzIiwgInJlc3RlY2ciLCAiZXhhbmciLCAidGhhbCJdCmZvciBjb2wgaW4gY2F0ZWdvcmljYWxfYXR0cjoKICB1Y2loZFtjb2xdID0gdWNpaGRbY29sXS5hc3R5cGUoImNhdGVnb3J5IikKCiMgQ2xlYW4gbGFiZWwuCnVjaWhkLmxvY1t1Y2loZFsibGFiZWwiXSA+IDEsICJsYWJlbCJdID0gMQoKcHJpbnQodWNpaGQuc2hhcGUpCnByaW50KHVjaWhkLmdyb3VwYnkoImxhYmVsIikuc2l6ZSgpKSAgIyBMYWJlbCBkaXN0cmlidXRpb24uCnByaW50KHVjaWhkLmhlYWQoKSkKYGBgCgpUaGUgZGF0YXNldCBjb250YWlucyBib3RoIG51bWVyaWNhbCBhbmQgY2F0ZWdvcmljYWwgZmVhdHVyZXMgKGFsbCBlbmNvZGVkIGluIG51bWVyaWNzIGFscmVhZHkpLgoKIyMjIEV4cGxhaW4gUmFuZG9tIEZvcmVzdAoKYGBge3B5dGhvbiB1Y2loZF9yZn0KIyBSRiBkb2Vzbid0IGFsbG93IG1pc3NpbmcgdmFsdWUuCiMgRm9yIGNhdGVnb3JpY2FsIChhcyBzdHJpbmcpIHdlIGNhbiBsZWF2ZSBvbmUgc3BlY2lhbCBjYXRlZ29yeSBmb3IgbWlzc2luZywKIyBidXQgZm9yIG51bWVyaWNhbCB3ZSBuZWVkIHRvIGRvIHNvbWUgc3BlY2lhbCBlbmNvZGluZyBvciBpbXB1dGF0aW9uLgp1Y2loZF8yID0gdWNpaGQuY29weSgpCnVjaWhkXzIubG9jW3VjaWhkXzJbImNhIl0uaXNuYSgpLCAiY2EiXSA9IC0xICAjIEVuY29kZSBtaXNzaW5nIG51bWVyaWNhbC4KCiMgT25lLWhvdCBlbmNvZGUgYWxsIGNhdGVnb3JpY2FsIGZlYXR1cmVzLgp1Y2loZF8yID0gcGQuZ2V0X2R1bW1pZXModWNpaGRfMiwgY29sdW1ucz1jYXRlZ29yaWNhbF9hdHRyLCBkdW1teV9uYT1UcnVlKQp1Y2loZF95ID0gdWNpaGRfMi5wb3AoImxhYmVsIikKdWNpaGRfWF90cmFpbiwgdWNpaGRfWF90ZXN0LCB1Y2loZF95X3RyYWluLCB1Y2loZF95X3Rlc3QgPSB0cmFpbl90ZXN0X3NwbGl0KAogIHVjaWhkXzIsIHVjaWhkX3kudmFsdWVzLCB0ZXN0X3NpemU9LjMsIHJhbmRvbV9zdGF0ZT02NCkKCnVjaWhkX3JmID0gUmFuZG9tRm9yZXN0Q2xhc3NpZmllcihuX2VzdGltYXRvcnM9MTAwLCByYW5kb21fc3RhdGU9NjQpCl8gPSB1Y2loZF9yZi5maXQodWNpaGRfWF90cmFpbiwgdWNpaGRfeV90cmFpbikKCnVjaWhkX3JmX3loYXQgPSB1Y2loZF9yZi5wcmVkaWN0X3Byb2JhKHVjaWhkX1hfdGVzdClbOiwxXQp1Y2loZF9yZl9wcmVkID0gdWNpaGRfcmYucHJlZGljdCh1Y2loZF9YX3Rlc3QpCgpwcmludChjbGFzc2lmaWNhdGlvbl9yZXBvcnQodWNpaGRfeV90ZXN0LCB1Y2loZF9yZl9wcmVkKSkKcHJpbnQocm9jX2F1Y19zY29yZSh1Y2loZF95X3Rlc3QsIHVjaWhkX3JmX3loYXQpKQpgYGAKCkFzIG9uZSBjYW4gc2VlIFJGIHBlcmZvcm1zIHZlcnkgd2VsbCBvbiB0aGlzIGRhdGFzZXQuCgpUbyBleHBsYWluIGEgbW9kZWwgdHJhaW5lZCB3aXRoIG51bWVyaWNhbCBmZWF0dXJlcywKYGxpbWVgIGJ5IGRlZmF1bHQgd2lsbCBkaXNjcmV0aXplIGNvbnRpbm91cyB2YXJpYWJsZXMgaW50byBxdWFudGlsZXMgZm9yIGVhc2Ugb2YgaW50ZXJwcmV0YXRpb24uCkRpc2NyZXRpemF0aW9uIGlzIGRvbmUgdXNpbmcgc3RhdGlzdGljcyBkZXJpdmVkIGZyb20gdGhlIHRyYWluaW5nIGRhdGFzZXQuCgpgYGB7cHl0aG9uIGxpbWVfdWNpaGRfcmZ9CmZyb20gbGltZS5saW1lX3RhYnVsYXIgaW1wb3J0IExpbWVUYWJ1bGFyRXhwbGFpbmVyCgpjYXRfaW5kID0gW2kgZm9yIGksIGNvbCBpbiBlbnVtZXJhdGUodWNpaGRfMi5jb2x1bW5zKSBpZiAiXyIgaW4gY29sXQp1Y2loZF9yZl9leHBsYWluZXIgPSBMaW1lVGFidWxhckV4cGxhaW5lcigKICB1Y2loZF9YX3RyYWluLnZhbHVlcywgY2xhc3NfbmFtZXM9WyJOZWdhdGl2ZSIsICJQb3NpdGl2ZSJdLAogIGZlYXR1cmVfbmFtZXM9dWNpaGRfMi5jb2x1bW5zLAogIGNhdGVnb3JpY2FsX2ZlYXR1cmVzPWNhdF9pbmQpCgp1Y2loZF9yZl90cF9pZHggPSBucC53aGVyZShucC5sb2dpY2FsX2FuZCh1Y2loZF9yZl9wcmVkID09IDEsIHVjaWhkX3lfdGVzdCA9PSAxKSlbMF0KdWNpaGRfcmZfZnBfaWR4ID0gbnAud2hlcmUobnAubG9naWNhbF9hbmQodWNpaGRfcmZfcHJlZCA9PSAxLCB1Y2loZF95X3Rlc3QgPT0gMCkpWzBdCgojIFdlIHRha2Ugb25lIHRydWUgcG9zaXRpdmUgYW5kIG9uZSBmYWxzZSBwb3NpdGl2ZSBmb3IgZXhhbXBsZXMuCnVjaWhkX3JmX3RwX2V4cCA9IHVjaWhkX3JmX2V4cGxhaW5lci5leHBsYWluX2luc3RhbmNlKAogIHVjaWhkX1hfdGVzdC5pbG9jW3VjaWhkX3JmX3RwX2lkeFswXV0sIHVjaWhkX3JmLnByZWRpY3RfcHJvYmEsIG51bV9mZWF0dXJlcz00KQp1Y2loZF9yZl9mcF9leHAgPSB1Y2loZF9yZl9leHBsYWluZXIuZXhwbGFpbl9pbnN0YW5jZSgKICB1Y2loZF9YX3Rlc3QuaWxvY1t1Y2loZF9yZl9mcF9pZHhbMF1dLCB1Y2loZF9yZi5wcmVkaWN0X3Byb2JhLCBudW1fZmVhdHVyZXM9NCkKCnVjaWhkX3JmX3RwX2V4cC5zYXZlX3RvX2ZpbGUoIi90bXAvZXhwbGFpbl90YWJfcmZfdHAuaHRtbCIpCnVjaWhkX3JmX2ZwX2V4cC5zYXZlX3RvX2ZpbGUoIi90bXAvZXhwbGFpbl90YWJfcmZfZnAuaHRtbCIpCmBgYAoKIyMjIyBBIFRydWUgUG9zaXRpdmUgUHJlZGljdGlvbiBFeHBsYWluZWQgey19CgpgYGB7ciwgZWNobz1GQUxTRX0KaHRtbHRvb2xzOjppbmNsdWRlSFRNTChwYXJzZV9saW1lX2h0bWxfb3V0cHV0KCIvdG1wL2V4cGxhaW5fdGFiX3JmX3RwLmh0bWwiKSkKYGBgCgojIyMjIEEgRmFsc2UgUG9zaXRpdmUgUHJlZGljdGlvbiBFeHBsYWluZWQgey19CgpgYGB7ciwgZWNobz1GQUxTRX0KaHRtbHRvb2xzOjppbmNsdWRlSFRNTChwYXJzZV9saW1lX2h0bWxfb3V0cHV0KCIvdG1wL2V4cGxhaW5fdGFiX3JmX2ZwLmh0bWwiKSkKYGBgCgoqKkRpc2N1c3MgdGhlIHR3byBleHBsYW5hdGlvbnMuKioKCiMjIyBFeHBsYWluIEdyYWRpZW50IEJvb3N0aW5nIFRyZWVzCgpHcmFkaWVudCBib29zdGluZyB0cmVlcyAoR0JUKSBpcyBhIHBvd2VyZnVsIG1vZGVsIGZhbWlseSBwcm92ZW4gdG8gd29yayBleGNlcHRpb25hbGx5IHdlbGwgaW4gbWFueSBkaWZmZXJlbnQgYXBwbGljYXRpb25zLgpZZXQgZHVlIHRvIGl0cyBlbnNlbWJsaW5nIG5hdHVyZSwKR0JUIGlzIGFsc28gaGFyZCB0byBpbnRyZXByZXQgaW4gZ2VuZXJhbC4KCkhlcmUgd2UgZGVtbyBgbGlnaHRnYm1gJ3MgaW1wbGVtZW50YXRpb24gb2YgR0JUIHdpdGggTElNRSBleHBsYW5hdGlvbi4KCmBgYHtweXRob24gdWNpaGRfbGdifQppbXBvcnQgbGlnaHRnYm0gYXMgbGdiCgp1Y2loZF90ciA9IGxnYi5EYXRhc2V0KHVjaWhkX1hfdHJhaW4sIGxhYmVsPXVjaWhkX3lfdHJhaW4pCnVjaWhkX3RlID0gbGdiLkRhdGFzZXQodWNpaGRfWF90ZXN0LCBsYWJlbD11Y2loZF95X3Rlc3QpCgp1Y2loZF9sZ2JfcGFyYW1zID0gewogICJsZWFybmluZ19yYXRlIjogLjAxLAogICJib29zdGluZ190eXBlIjogImdiZHQiLAogICJvYmplY3RpdmUiOiAiYmluYXJ5IiwKICAibWV0cmljIjogWyJiaW5hcnlfbG9nbG9zcyIsICJhdWMiXSwKICAibnVtX2xlYXZlcyI6IDQsCiAgIm1heF9kZXB0aCI6IDIsCiAgIm1pbl9kYXRhX3Blcl9sZWFmIjogNSwKICAidmVyYm9zZSI6IC0xLAogICJzZWVkIjogNjQKfQoKdWNpaGRfYnN0ID0gbGdiLnRyYWluKAogIHBhcmFtcz11Y2loZF9sZ2JfcGFyYW1zLAogIG51bV9ib29zdF9yb3VuZD0zMDAsIGVhcmx5X3N0b3BwaW5nX3JvdW5kcz0yMCwKICB0cmFpbl9zZXQ9dWNpaGRfdHIsIHZhbGlkX3NldHM9W3VjaWhkX3RlXSwKICB2ZXJib3NlX2V2YWw9MTApCgp1Y2loZF9sZ2JfeWhhdCA9IHVjaWhkX2JzdC5wcmVkaWN0KHVjaWhkX1hfdGVzdCkKdWNpaGRfbGdiX3ByZWQgPSAodWNpaGRfbGdiX3loYXQgPiAuNSkuYXN0eXBlKGludCkKCnByaW50KGNsYXNzaWZpY2F0aW9uX3JlcG9ydCh1Y2loZF95X3Rlc3QsIHVjaWhkX2xnYl9wcmVkKSkKcHJpbnQocm9jX2F1Y19zY29yZSh1Y2loZF95X3Rlc3QsIHVjaWhkX2xnYl95aGF0KSkKYGBgCgpJbiB0aGlzIHBhcnRpY3VsYXIgKHJhdGhlciBzbWFsbCkgZGF0YXNldCBSRiBpbmRlZWQgb3V0cGVyZm9ybXMgR0JULgpBcyBhIG1hdHRlciBvZiBmYWN0LApiYXNlZCBvbiBbZXhpc3RpbmcgYmVuY2htYXJrXShodHRwczovL2dpdGh1Yi5jb20vaW50ZXJwcmV0bWwvaW50ZXJwcmV0L3RyZWUvbWFzdGVyL2JlbmNobWFya3MpIGEgc2ltcGxlIGxvZ2lzdGljIHJlZ3Jlc3Npb24gbWF5IGhhdmUgYSBldmVuIGhpZ2hlciBzY29yZSBmb3IgdGhpcyBwcm9ibGVtLgpOZXZlcnRoZWxlc3MsIGxldCdzIG1vdmUgb24gdG8gb3VyIGV4cGxhbmF0aW9uIG1vZGVsIHdpdGggTElNRToKCmBgYHtweXRob24gbGltZV91Y2loZF9sZ2J9CmRlZiB1Y2loZF9sZ2JfcHJlZGljdF9mbih4KToKICAjIFdlIG5lZWQgdG8gb3V0cHV0IDIgY29sdW1ucyBmb3IgYmluYXJ5IHByb2IgcHJlZGljdGlvbi4KICBwID0gdWNpaGRfYnN0LnByZWRpY3QoeCkucmVzaGFwZSgtMSwgMSkKICByZXR1cm4gbnAuaHN0YWNrKCgxIC0gcCwgcCkpCgp1Y2loZF9sZ2JfZXhwbGFpbmVyID0gTGltZVRhYnVsYXJFeHBsYWluZXIoCiAgdWNpaGRfWF90cmFpbi52YWx1ZXMsIGNsYXNzX25hbWVzPVsiTmVnYXRpdmUiLCAiUG9zaXRpdmUiXSwKICBmZWF0dXJlX25hbWVzPXVjaWhkXzIuY29sdW1ucywKICBjYXRlZ29yaWNhbF9mZWF0dXJlcz1jYXRfaW5kKQoKIyBXZSB0YWtlIHRoZSBzYW1lIGV4YW1wbGVzIHByZXZpb3VzbHkgZXhwbGFpbmVkIGluIG91ciBSRiBleHBsYW5hdGlvbiBtb2RlbC4KdWNpaGRfbGdiX3RwX2V4cCA9IHVjaWhkX2xnYl9leHBsYWluZXIuZXhwbGFpbl9pbnN0YW5jZSgKICB1Y2loZF9YX3Rlc3QuaWxvY1t1Y2loZF9yZl90cF9pZHhbMF1dLCB1Y2loZF9sZ2JfcHJlZGljdF9mbiwgbnVtX2ZlYXR1cmVzPTQpCnVjaWhkX2xnYl9mcF9leHAgPSB1Y2loZF9sZ2JfZXhwbGFpbmVyLmV4cGxhaW5faW5zdGFuY2UoCiAgdWNpaGRfWF90ZXN0Lmlsb2NbdWNpaGRfcmZfZnBfaWR4WzBdXSwgdWNpaGRfbGdiX3ByZWRpY3RfZm4sIG51bV9mZWF0dXJlcz00KQoKdWNpaGRfbGdiX3RwX2V4cC5zYXZlX3RvX2ZpbGUoIi90bXAvZXhwbGFpbl90YWJfbGdiX3RwLmh0bWwiKQp1Y2loZF9sZ2JfZnBfZXhwLnNhdmVfdG9fZmlsZSgiL3RtcC9leHBsYWluX3RhYl9sZ2JfZnAuaHRtbCIpCmBgYAoKYGBge3IsIGVjaG89RkFMU0V9Cmh0bWx0b29sczo6aW5jbHVkZUhUTUwocGFyc2VfbGltZV9odG1sX291dHB1dCgiL3RtcC9leHBsYWluX3RhYl9sZ2JfdHAuaHRtbCIpKQpgYGAKCmBgYHtyLCBlY2hvPUZBTFNFfQpodG1sdG9vbHM6OmluY2x1ZGVIVE1MKHBhcnNlX2xpbWVfaHRtbF9vdXRwdXQoIi90bXAvZXhwbGFpbl90YWJfbGdiX2ZwLmh0bWwiKSkKYGBgCgoqKlRPRE86IERpc2N1c3Npb24gb24gdGhlIGV4cGxhbmF0aW9uLioqCgojIyMjIE9wdGltaXplZCBDYXRlZ29yaWNhbCBFbmNvZGluZyBpbiBgbGlnaHRnYm1gIHstfQoKKipUaGlzIHNlY3Rpb24gaXMgYSBkaWdyZXNzaW9uIG9uIGBsaWdodGdibWAgdXNhZ2UuKioKClNpbmNlIGBsaW1lYCdzIEFQSSByZXF1aXJlcyB1cyB0byBwcmVwYXJlIG91ciBkYXRhc2V0IGluIG9uZS1ob3QgZW5jb2RpbmcgcmVwcmVzZW50YXRpb24sCm91ciBgbGlnaHRnYm1gIGNvZGUgdXNlIHRoZSBzYW1lIGRhdGEgcGlwZWxpbmUgYXMgaW4gYHNjaWtpdC1sZWFybmAgcmFuZG9tIGZvcmVzdC4KQnV0IHRoYXQgaXMgYWN0dWFsbHkgbm90IG9wdGltaXplZCBmb3IgYGxpZ2h0Z2JtYC4KVGhlIGZvbGxvd2luZyBjb2RlIGNodW5rIHNob3djYXNlcyB0aGUgYmVzdCBwcmFjdGljZSBvZiBlbmNvZGluZyBjYXRlZ29yaWNhbHMgaW4gYGxpZ2h0Z2JtYDoKV2UgZG9uJ3QgZW5jb2RlIHRoZW0gYXQgYWxsIQoKYGBge3B5dGhvbiBsZ2JfYmVzdF9wcmFjdGljZX0KIyBXZSBsZWF2ZSBib3RoIG1pc3NpbmdzIGFuZCBjYXRlZ29yaWNhbHMgYXMtaXMgaW4gdGhlIGRhdGFzZXQuCnVjaWhkX3RyYWluLCB1Y2loZF90ZXN0ID0gdHJhaW5fdGVzdF9zcGxpdCh1Y2loZCwgdGVzdF9zaXplPS4zLCByYW5kb21fc3RhdGU9NjQpCnVjaWhkX3RyID0gbGdiLkRhdGFzZXQoCiAgdWNpaGRfdHJhaW4uZHJvcCgibGFiZWwiLCBheGlzPTEpLCBsYWJlbD11Y2loZF90cmFpblsibGFiZWwiXSwKICBjYXRlZ29yaWNhbF9mZWF0dXJlPWNhdGVnb3JpY2FsX2F0dHIsCiAgZnJlZV9yYXdfZGF0YT1GYWxzZSkKdWNpaGRfdGUgPSBsZ2IuRGF0YXNldCgKICB1Y2loZF90ZXN0LmRyb3AoImxhYmVsIiwgYXhpcz0xKSwgbGFiZWw9dWNpaGRfdGVzdFsibGFiZWwiXSwKICBjYXRlZ29yaWNhbF9mZWF0dXJlPWNhdGVnb3JpY2FsX2F0dHIsCiAgZnJlZV9yYXdfZGF0YT1GYWxzZSkKCnVjaWhkX2JzdF8yID0gbGdiLnRyYWluKAogIHBhcmFtcz11Y2loZF9sZ2JfcGFyYW1zLAogIG51bV9ib29zdF9yb3VuZD0zMDAsIGVhcmx5X3N0b3BwaW5nX3JvdW5kcz0yMCwKICB0cmFpbl9zZXQ9dWNpaGRfdHIsIHZhbGlkX3NldHM9W3VjaWhkX3RlXSwKICB2ZXJib3NlX2V2YWw9LTEpCgp1Y2loZF9sZ2JfeWhhdCA9IHVjaWhkX2JzdF8yLnByZWRpY3QodWNpaGRfdGVzdC5kcm9wKCJsYWJlbCIsIGF4aXM9MSkpCnVjaWhkX2xnYl9wcmVkID0gKHVjaWhkX2xnYl95aGF0ID4gLjUpLmFzdHlwZShpbnQpCgpwcmludChyb2NfYXVjX3Njb3JlKHVjaWhkX3Rlc3RbImxhYmVsIl0sIHVjaWhkX2xnYl95aGF0KSkKYGBgCgpUbyBzdW1tYXJpemUsClRoZXJlIGFyZSB0d28gdmVyeSBzcGVjaWFsIHByb3BlcnRpZXMgYWJvdXQgYGxpZ2h0Z2JtYCBhbGdvcml0aG0uCmBsaWdodGdibWAgdHJlYXRzIG1pc3NpbmdzIG5hdGl2ZWx5IGFzIGEgc3BlY2lhbCB0cmVlIHNwbGl0IHBvaW50LgpUaGlzIGFsbG93cyB1cyB0byBrZWVwIHRoZSBvcmlnaW5hbCBtaXNzaW5nIGFzIGlzIGFuZCBpbiBtYW55IGNhc2VzIGNhbiByZXN1bHQgaW4gYmV0dGVyIGFjY3VyYWN5IHRoYW4gaW1wdXRhdGlvbi5eW2B4Z2Jvb3N0YCBpcyB0aGUgZmlyc3QgdG8gaW50cm9kdWNlIHN1Y2ggbWlzc2luZyB0cmVhdG1lbnQgYW1vbmcgYWxsIHRoZSBHQlQgcGFja2FnZS4gYGxpZ2h0Z2JtYCBmb2xsb3dzLl0KCkluIGFkZGl0aW9uLApgbGlnaHRnYm1gIGVuY29kZXMgY2F0ZWdvcmljYWwgdmFyaWFibGVzIGludGVybmFsbHkgaW4gYSBtb3JlIGVmZmljaWVudCB3YXkuClNvIHdlIGRvbid0IGV2ZW4gbmVlZCB0byBkbyBvbmUtaG90IGVuY29kaW5nIG9uIG91ciBvd24uCk9mIGNvdXJzZSBpbiB0aGlzIHRpbnkgZGF0YXNldCB3ZSB3b24ndCBzZWUgYW55IG5vdGljYWJsZSBkaWZmZXJlbmNlLgpCdXQgZm9yIGxhcmdlIGFwcGxpY2F0aW9ucyB0aGUgaW1wYWN0IGNhbiBiZSBodWdlLgpXaGF0ZXZlciwKYnkgc2tpcHBpbmcgb25lLWhvdCBlbmNvZGluZyBwaXBlbGluZSBvdXIgY29kZSBjYW4gYmUgbXVjaCBuZWF0ZXIgYXMgd2VsbC4KCiMjIE9uIEltYWdlIENsYXNzaWZpZXIKCioqVE9ETzogVXNlIGEgcHJlLXRyYWluZWQgbW9kZWw/KioKCiMgU2hhcGxleSBSZWdyZXNzaW9uIFZhbHVlcwoKKipUT0RPOiBUaGVvcnkgQnJpZWZpbmcgaGVyZS4qKgoKIyBTSEFQCgpATklQUzIwMTdfNzA2MiBwcm9wb3NlIFNIQVAgKCoqU0hhcGxleSBBZGRpdGl2ZSBleFBsYW5hdGlvbnMqKiksCnlldCBhbm90aGVyIGFkZGl0aXZlIGZlYXR1cmUgYXR0cmlidXRpb24gbWV0aG9kIGZvciBtb2RlbCBleHBsYWluYWJpbGl0eS4KSXQgaXMgYSBtb3JlIGdlbmVyYWwgYXBwcm9hY2ggd2hlcmUgTElNRSBpcyBpbmRlZWQgb25seSBhIHNwZWNpYWwgY2FzZSBvZiBpdC4KSnVzdCBsaWtlIExJTUUsCmluIHRoZW9yeSBpdCBjYW4gYmUgYXBwbGllZCB0byAqYW55KiBtYWNoaW5lIGxlYXJuaW5nIG1vZGVsLApidXQgY29tZXMgd2l0aCBhIGN1c3RvbWl6ZWQgZmFzdCBpbXBsZW1lbnRhdGlvbiBwYXJ0aWN1bGFybHkgZm9yIGdyYWRpZW50IGJvb3N0aW5nIHRyZWVzIChHQlQpLgpJdCBzdXBwb3J0cyBBUElzIG9mIHdlbGwta25vd24gR0JUIGxpYnJhcmllcyBzdWNoIGFzCltgeGdib29zdGBdKGh0dHBzOi8vZ2l0aHViLmNvbS9kbWxjL3hnYm9vc3QpLApbYGxpZ2h0Z2JtYF0oaHR0cHM6Ly9naXRodWIuY29tL21pY3Jvc29mdC9MaWdodEdCTSksCmFuZCBbYGNhdGJvb3N0YF0oaHR0cHM6Ly9naXRodWIuY29tL2NhdGJvb3N0L2NhdGJvb3N0KS4KClRoZSBpbnRlcnByZXRhYmlsaXR5IHByb3ZpZGVkIGJ5IFNIQVAgaXMgYWdhaW4gKmxvY2FsKi4KSXQgYXNzaWducyBlYWNoIGZlYXR1cmUgYW4gaW1wb3J0YW5jZSB2YWx1ZSAqZm9yIGEgcGFydGljdWxhciBwcmVkaWN0aW9uLioKSGVuY2UgaXQgcHJvdmlkZXMgZm9yIGFueSBnaXZlbiBtb2RlbCBwcmVkaWN0aW9uIHdoYXQgbWF5IGJlIHRoZSBkcml2aW5nIGZvcmNlIGZvciB0aGUgbW9kZWwgdG8gbWFrZSBzdWNoIHByZWRpY3Rpb24uCgpgc2hhcGAgYWxzbyBjb21lcyB3aXRoIG1vcmUgdmlzdWFsaXphdGlvbiBtZXRob2RzIGZvciBmZWF0dXJlIGludmVzdGlnYXRpb24sCmVzcGVjaWFsbHkgZm9yIGZlYXR1cmUgaW50ZXJhY3Rpb24gZXhwbG9yYXRpb24uCgoqKlRPRE86IFRoZW9yeSBCcmllZmluZyBoZXJlLioqCgojIyBPbiBUZXh0IENsYXNzaWZpZXJzCgojIyMgRXhwbGFpbiBSYW5kb20gRm9yZXN0Cgpgc2hhcC5UcmVlRXhwbGFpbmVyYCBpcyBvcHRpbWl6ZWQgZm9yIEdCVCBidXQgbm90IFJGLgpGb3IgbW9kZWwgd2l0aCBoaWdoIGRpbWVuc2lvbmFsaXR5IGxpa2UgYSBiYWctb2Ytd29yZHMgbW9kZWwgaXQgd2lsbCBzdWZmZXIgZnJvbSBoaWdoIGNvbXB1dGF0aW9uIGNvc3QgZm9yIG5vbi1HQlQgbW9kZWwuCkhlbmNlIHdlIHdpbGwgc2tpcCB0aGUgZGlzY3Vzc2lvbiBvbiBSRiBhbmQgbW92ZSBmb3J3YXJkIHRvIGEgR0JUIGltcGxlbWVudGF0aW9uLgoKIyMjIEV4cGxhaW4gR3JhZGllbnQgQm9vc3RpbmcgVHJlZXMKCkluIHRoZSBwcmV2aW91cyBzZWN0aW9uIHdlIGRpZG4ndCB0cmFpbiBhIEdCVCBmb3IgdGhlIHRleHQgY2xhc3NpZmljYXRpb24gcHJvYmxlbS4KU28gbGV0J3MgcXVpY2tseSBidWlsZCBvbmUgc3VjaCBtb2RlbCBmaXJzdCAod2l0aCB0aGUgc2FtZSBURi1JREYgdmVjdG9yaXphdGlvbiBhcyB3ZSBkaWQgZm9yIHRoZSByYW5kb20gZm9yZXN0IG1vZGVsKS4KCmBgYHtweXRob24gaW1kYl9sZ2J9CiMgbGlnaHRnYm0gZG9lcyBub3QgYWxsb3cgdXRmLTggZW5jb2RlZCBmZWF0dXJlIG5hbWVzLgojIFNpbmNlIGltcG9ydGFudCB0b2tlbnMgYXJlIG1vc3QgbGlrZWx5IGFzY2lpLWNvbXBhdGlibGUgZm9yIG91ciBkYXRhc2V0LAojIHdlIHNpbXBseSBzdHJpcCBub24tYXNjaWkgYXMgYSB3b3JrYXJvdW5kIGZvciB0aGlzIGV4ZXJjaXNlLgpkZWYgcmVtb3ZlX25vbl9hc2NpaShzKToKICByZXR1cm4gIiIuam9pbihbaSBpZiBvcmQoaSkgPCAxMjggZWxzZSAiXyIgZm9yIGkgaW4gc10pCgpzb3J0ZWRfdm9jYWJfYXNjaWkgPSBbcmVtb3ZlX25vbl9hc2NpaSh2KSBmb3IgdiBpbiBzb3J0ZWRfdm9jYWJdCgppbWRiX1hfdHIgPSBsZ2IuRGF0YXNldChpbWRiX1hfdHJhaW4sIGxhYmVsPWltZGJfeV90cmFpbiwgZmVhdHVyZV9uYW1lPXNvcnRlZF92b2NhYl9hc2NpaSkKaW1kYl9YX3RlID0gbGdiLkRhdGFzZXQoaW1kYl9YX3Rlc3QsIGxhYmVsPWltZGJfeV90ZXN0LCBmZWF0dXJlX25hbWU9c29ydGVkX3ZvY2FiX2FzY2lpKQoKaW1kYl9sZ2JfcGFyYW1zID0gewogICJsZWFybmluZ19yYXRlIjogLjA1LAogICJib29zdGluZ190eXBlIjogImdiZHQiLAogICJvYmplY3RpdmUiOiAiYmluYXJ5IiwKICAibWV0cmljIjogWyJiaW5hcnlfbG9nbG9zcyIsICJhdWMiXSwKICAibnVtX2xlYXZlcyI6IDE2LAogICJtYXhfZGVwdGgiOiA0LAogICJtaW5fZGF0YV9wZXJfbGVhZiI6IDIwLAogICJ2ZXJib3NlIjogLTEKfQoKaW1kYl9sZ2JfbW9kZWxfZmlsZSA9ICJtb2RlbHMvdGV4dF9jbGZfbGdiLnR4dCIKCiMgU2F2ZS9yZWxvYWQgbW9kZWwgdG8gc2F2ZSBub3RlYm9vayByZW5kZXJpbmcgdGltZS4KaWYgb3MucGF0aC5leGlzdHMoaW1kYl9sZ2JfbW9kZWxfZmlsZSk6CiAgIyBUT0RPOgogICMgUGFyYW1ldGVycyBhcmUgbm90IGxvYWRlZCBiYWNrPyBBIGJ1Zz8gKFdoaWNoIGNhdXNlIHRoZSBzdWJzZXF1ZW50IGNhbGwgdG8gc2hhcF92YWx1ZXMgZmFpbC4pCiAgIyBodHRwczovL2dpdGh1Yi5jb20vbWljcm9zb2Z0L0xpZ2h0R0JNL2lzc3Vlcy8yNjEzCiAgaW1kYl9ic3QgPSBsZ2IuQm9vc3Rlcihtb2RlbF9maWxlPWltZGJfbGdiX21vZGVsX2ZpbGUsIHBhcmFtcz1pbWRiX2xnYl9wYXJhbXMpCmVsc2U6CiAgaW1kYl9ic3QgPSBsZ2IudHJhaW4oCiAgICBwYXJhbXM9aW1kYl9sZ2JfcGFyYW1zLAogICAgbnVtX2Jvb3N0X3JvdW5kPTEwMDAsIGVhcmx5X3N0b3BwaW5nX3JvdW5kcz0yMCwKICAgIHRyYWluX3NldD1pbWRiX1hfdHIsIHZhbGlkX3NldHM9W2ltZGJfWF90ZV0sCiAgICB2ZXJib3NlX2V2YWw9MTAwKQogIF8gPSBpbWRiX2JzdC5zYXZlX21vZGVsKGltZGJfbGdiX21vZGVsX2ZpbGUpCgppbWRiX2xnYl95aGF0ID0gaW1kYl9ic3QucHJlZGljdChpbWRiX1hfdGVzdCkKaW1kYl9sZ2JfcHJlZCA9IChpbWRiX2xnYl95aGF0ID4gLjUpLmFzdHlwZShpbnQpCgpwcmludChjbGFzc2lmaWNhdGlvbl9yZXBvcnQoaW1kYl95X3Rlc3QsIGltZGJfbGdiX3ByZWQpKQpwcmludChyb2NfYXVjX3Njb3JlKGltZGJfeV90ZXN0LCBpbWRiX2xnYl95aGF0KSkKYGBgCgpKdXN0IGxpa2UgUkYgd2Ugd2lsbCBoYXZlIGFjY2VzcyB0byB0aGUgb3ZlcmFsbCBmZWF0dXJlIGltcG9ydGFuY2Ugd2l0aCBhIEdCVCBtb2RlbDpeW0J5IGRlZmF1bHQgYGxpZ2h0Z2JtYCBjYWxjdWxhdGUgdGhlIGltcG9ydGFuY2UgYnkgY291bnRpbmcgaG93IG1hbnkgdGltZXMgYSBmZWF0dXJlIGNvbnRyaWJ1dGUgdG8gYW4gb3B0aW1hbCBzcGxpdCBkdXJpbmcgbW9kZWwgdHJhaW5pbmcuCkl0IGFsc28gc3VwcG9ydHMgdGhlIGltcHVyaXR5LWJhc2VkIGFwcHJvYWNoIHdpdGggYXJndW1lbnQgYGltcG9ydGFuY2VfdHlwZWAgc2V0IHRvIGAiZ2FpbiJgLl0KCmBgYHtweXRob24gaW1kYl9sZ2JfZmVhdF9pbXB9CmF4ID0gbGdiLnBsb3RfaW1wb3J0YW5jZShpbWRiX2JzdCwgbWF4X251bV9mZWF0dXJlcz0yMCkKcGx0LnNob3coKQpgYGAKCk5vdyBmb3IgdGhlIGV4cGxhbmF0aW9uIG1vZGVsLApzaW5jZSBgc2hhcC5UcmVlRXhwbGFpbmVyYCBpcyBjdXN0b21pemVkIGZvciBHQlQgZm9yIHNwZWVkLAp3ZSBjYW4gZmVlZCBpbiBhbGwgdGVzdGluZyBleGFtcGxlcyB0byBjYWxjdWxhdGUgYWxsIHNoYXAgdmFsdWVzIGF0IG9uY2UuCgpgYGB7cHl0aG9uIHNoYXBfaW1kYl9sZ2J9CmltcG9ydCBzaGFwCgojIFNwYXJzZSBtYXRyaXggaXMgc3VwcG9ydGVkIGJ5IHNoYXAgZm9yIGxpZ2h0Z2JtIG1vZGVscy4KaW1kYl9sZ2JfZXhwbGFpbmVyID0gc2hhcC5UcmVlRXhwbGFpbmVyKGltZGJfYnN0KQppbWRiX2xnYl9zaGFwX3ZhbHVlcyA9IGltZGJfbGdiX2V4cGxhaW5lci5zaGFwX3ZhbHVlcyhpbWRiX1hfdGVzdCkKCmRlZiBpbWRiX2xnYl9zaGFwX3Bsb3QodGVzdF9pZCwgbWF0cGxvdGxpYj1UcnVlKToKICBzaGFwX3BsdCA9IHNoYXAuZm9yY2VfcGxvdCgKICAgIGltZGJfbGdiX2V4cGxhaW5lci5leHBlY3RlZF92YWx1ZVsxXSwKICAgIGltZGJfbGdiX3NoYXBfdmFsdWVzWzFdW3Rlc3RfaWQsOl0sCiAgICBpbWRiX1hfdGVzdFt0ZXN0X2lkLDpdLnRvYXJyYXkoKSwgICMgV2Ugc3RpbGwgbmVlZCBhIGRlbnNlIG1hdHJpeCBoZXJlLgogICAgZmVhdHVyZV9uYW1lcz1zb3J0ZWRfdm9jYWIsCiAgICBtYXRwbG90bGliPW1hdHBsb3RsaWIKICApCiAgcmV0dXJuIHNoYXBfcGx0CmBgYAoKIyMjIyBHbG9iYWwgSW1wb3J0YW5jZSB7LX0KCldlIGNhbiBkZXJpdmUgZ2xvYmFsIGltcG9ydGFuY2UgYmFzZWQgb24gc2hhcCB2YWx1ZXMuCk5vdGUgdGhhdCB0aGlzIGlzIGRpZmZlcmVudCBmcm9tIHRoZSBsb3NzL2ltcHVyaXR5IG9yIHNwbGl0IHRpbWUtYmFzZWQgZmVhdHVyZSByYW5raW5nIGRlcml2ZWQgZnJvbSBSRi9HQlQgKmR1cmluZyB0cmFpbmluZyouCkl0IGlzIGFuIGFnZ3JlZ2F0aW9uIGZyb20gYWxsIGxvY2FsIHByZWRpY3Rpb24gZXhwbGFuYXRpb25zIChjb250cmlidXRpb25zKSAqZHVyaW5nIHRlc3RpbmcgZGF0YSBpbmZlcmVuY2UqLgoKYGBge3B5dGhvbiBzaGFwX2ltZGJfbGdiX2ZlYXRfaW1wfQpzaGFwLnN1bW1hcnlfcGxvdChpbWRiX2xnYl9zaGFwX3ZhbHVlcywgaW1kYl9YX3Rlc3QsIGZlYXR1cmVfbmFtZXM9c29ydGVkX3ZvY2FiLAogICAgICAgICAgICAgICAgICBwbG90X3R5cGU9ImJhciIsIG1heF9kaXNwbGF5PTIwLCBzaG93PUZhbHNlKQpwbHQuc2hvdygpCmBgYAoKIyMjIyBMb2NhbCBFeHBsYW5hdGlvbiB7LX0KCmBgYHtweXRob259CmltZGJfbGdiX3NoYXBfcGxvdChpbWRiX3JmX3RwX2lkeFswXSkKYGBgCgpgYGB7cHl0aG9ufQppbWRiX2xnYl9zaGFwX3Bsb3QoaW1kYl9yZl9mcF9pZHhbMF0pCmBgYAoKKipUT0RPOiBEaXNjdXNzIHRoZSByZXN1bHQuIEFueSB0aGluZyBkaWZmZXJlbnQgZnJvbSBMSU1FPyoqCgpCeSBkZWZhdWx0IGBzaGFwYCBmb3IgYGxpZ2h0Z2JtYCBzaG93cyBsb2ctb2RkcyByYXRoZXIgdGhhbiBwcm9iYWJpbGl0eSBpbiB0aGUgcGxvdC4KVG8gdmVyaWZ5IHRoaXM6CgpgYGB7cHl0aG9uIHZlcmlmeV9sb2dfb2Rkc30KIyBUYWtlIHRoZSBmaXJzdCB0cnVlIHBvc2l0aXZlIHRvIGV4YW1pbmU6CnAgPSBpbWRiX2JzdC5wcmVkaWN0KGltZGJfWF90ZXN0W2ltZGJfcmZfdHBfaWR4WzBdLDpdLnRvYXJyYXkoKSkKcHJpbnQocCkKcHJpbnQobnAubG9nKHAgLyAoMSAtIHApKSkKYGBgCgojIyMgRXhwbGFpbiBOZXVyYWwgTmV0cyB3aXRoIFdvcmQgRW1iZWRkaW5ncwoKQXMgb2YgYHIgZm9ybWF0KFN5cy50aW1lKCksICclWS0lbS0lZCcpYCBgRGVlcEV4cGxhaW5lcmAgZG9lcyBub3QgeWV0IHN1cHBvcnQgVEYgMi4wLl5baHR0cHM6Ly9naXRodWIuY29tL3NsdW5kYmVyZy9zaGFwL2lzc3Vlcy84NTAuXQpBbmQgYEdyYWRpZW50RXhwbGFpbmVyYCBpcyBub3Qgd2VsbCBkb2N1bWVudGVkIHlldCBmb3IgVEYgMi4wLgpTbyB3ZSB3aWxsIHVzZSB0aGUgYEtlcm5lbEV4cGxhaW5lcmAgd2hpY2ggaXMgYSBpbXBsZW1lbnRhdGlvbi1hZ25vc3RpYyBleHBsYWluZXIgaW4gYHNoYXBgLgpUaGUgY29tcHJvbWlzZSBpcyB0aGF0IGl0IHdpbGwgcnVuIHZlcnkgc2xvdyBmb3IgZWFjaCBwcmVkaWN0aW9uLgoKYGBge3B5dGhvbiBzaGFwX2tlcm5lbF9pbWRiX25ufQppbWRiX2V4cF9pbmQgPSBucC5hcnJheShbaW1kYl9yZl90cF9pZHhbMF0sIGltZGJfcmZfZnBfaWR4WzBdXSkKIyBLZXJuZWxFeHBsYWluZXIuCmRlZiBtbShYKToKICByZXR1cm4gaW1kYl90ci5wcmVkaWN0X3Byb2JhKFgpWzosMV0KCmltZGJfbm5fc2hhcF9leHBsYWluZXIgPSBzaGFwLktlcm5lbEV4cGxhaW5lcihtbSwgc2VxX3RyYWluX3BhZGRlZFs6MTAwXSkKIyBUaGlzIGlzIFZFUlkgc2xvdy4uLgppbWRiX25uX2tlcm5lbF9zaGFwX3ZhbHVlcyA9IGltZGJfbm5fc2hhcF9leHBsYWluZXIuc2hhcF92YWx1ZXMoc2VxX3Rlc3RfcGFkZGVkW2ltZGJfZXhwX2luZF0pCiMgVE9ETzoKIyBDb250cmlidXRpb24gaXMgYXR0cmlidXRlZCB0byBvcmlnaW5hbCBzZXF1ZW5jZSBpbnB1dC4KIyBJbiBvcmRlciB0byBtYWtlIGV4cGxhbmF0aW9uIHJlYWRhYmxlLAojIHdlIG5lZWQgdG8gbWFwIGVhY2ggcG9zaXRpb24gdG8gb3JpZ2luYWwgd29yZCBpZCB0aGVuIHRvIHdvcmQuCmBgYAoKYGBgcHl0aG9uCiMgVE9ETzogTWFramUgc3VyZSBldmVyeXRoaW5nIHdvcmtzIGhlcmUuCgojIHNoYXAgZG9lcyBub3Qgc3VwcG9ydCBrZXJhcyBtb2RlbCBpbiBzY2lraXQtbGVhcm4gd3JhcHBlci4KIyBMZXQncyByZS1idWlsZCB0aGUgbW9kZWwgYW5kIHJldGFpbiBpdHMgU2VxdWVudGFsIGNsYXNzLgpkbF9tb2RlbCA9IG1vZGVsX2ZuKCkKbWV0cmljcyA9IGRsX21vZGVsLmZpdCgKICB4PXNlcV90cmFpbl9wYWRkZWQsIHk9aW1kYl95X3RyYWluLAogIGJhdGNoX3NpemU9MjU2LCBlcG9jaHM9MjAsCiAgdmFsaWRhdGlvbl9kYXRhPShzZXFfdGVzdF9wYWRkZWQsIGltZGJfeV90ZXN0KSwKICB2YWxpZGF0aW9uX3N0ZXBzPTIwLAogIGNhbGxiYWNrcz1bCiAgICB0Zi5rZXJhcy5jYWxsYmFja3MuRWFybHlTdG9wcGluZyhtb25pdG9yPSJ2YWxfbG9zcyIsIHBhdGllbmNlPTIpLAogICAgdGYua2VyYXMuY2FsbGJhY2tzLk1vZGVsQ2hlY2twb2ludCh0cl9tb2RlbF9maWxlLCBtb25pdG9yPSJ2YWxfbG9zcyIsIHNhdmVfYmVzdF9vbmx5PVRydWUpCiAgXSwKICB2ZXJib3NlPTApCgojIERlZXBFeHBsYWluZXIuCmRsX3NoYXBfZXhwbGFpbmVyID0gc2hhcC5EZWVwRXhwbGFpbmVyKGRsX21vZGVsLCBzZXFfdHJhaW5fcGFkZGVkKSAgIyBXb250JyB3b3JrLgoKIyBHcmFkaWVudEV4cGxhaW5lci4KaW1kYl9ubl9zaGFwX2V4cGxhaW5lciA9IHNoYXAuR3JhZGllbnRFeHBsYWluZXIoZGxfbW9kZWwsIHNlcV90cmFpbl9wYWRkZWRbOjEwMF0pCgppbWRiX25uX3NoYXBfZXhwbGFpbmVyID0gc2hhcC5HcmFkaWVudEV4cGxhaW5lcigKICAoaW1kYl90ci5sYXllcnNbMF0uaW5wdXQsIGltZGJfdHIubGF5ZXJzWy0xXS5vdXRwdXQpLCAgIyBOb3Qgd29ya2luZyBmb3IgVEYgMi4wLgogIHNlcV90cmFpbl9wYWRkZWRbOjEwMF0pCmltZGJfbm5fc2hhcF9leHBsYWluZXIuc2hhcF92YWx1ZXMoc2VxX3Rlc3RfcGFkZGVkWzozXSkgICMgRXJyb3IgaGVyZS4KYGBgCgojIyBPbiBUYWJ1bGFyIERhdGEgQ2xhc3NpZmllcgoKIyMjIEV4cGxhaW4gUmFuZG9tIEZvcmVzdAoKYGBge3B5dGhvbiBzaGFwX3VjaWhkX3JmfQp1Y2loZF9yZl9leHBsYWluZXIgPSBzaGFwLlRyZWVFeHBsYWluZXIodWNpaGRfcmYpCnVjaWhkX3JmX3NoYXBfdmFsdWVzID0gdWNpaGRfcmZfZXhwbGFpbmVyLnNoYXBfdmFsdWVzKHVjaWhkX1hfdGVzdCkKCmRlZiB1Y2loZF9yZl9zaGFwX3Bsb3QodGVzdF9pZCwgbWF0cGxvdGxpYj1UcnVlKToKICBzaGFwX3BsdCA9IHNoYXAuZm9yY2VfcGxvdCgKICAgIHVjaWhkX3JmX2V4cGxhaW5lci5leHBlY3RlZF92YWx1ZVsxXSwKICAgIHVjaWhkX3JmX3NoYXBfdmFsdWVzWzFdW3Rlc3RfaWQsOl0sCiAgICB1Y2loZF9YX3Rlc3QuaWxvY1tbdGVzdF9pZF1dLAogICAgbWF0cGxvdGxpYj1tYXRwbG90bGliCiAgKQogIHJldHVybiBzaGFwX3BsdApgYGAKCiMjIyMgR2xvYmFsIEZlYXR1cmUgSW1wb3J0YW5jZSB7LX0KCiMjIyMjIFNwbGl0LXRpbWUtYmFzZWQgZmVhdHVyZSByYW5raW5nIHstfQoKYGBge3B5dGhvbiB1Y2loZF9yZl9mZWF0X2ltcH0KdWNpaGRfcmZfZmVhdF9pbXAgPSBwZC5TZXJpZXModWNpaGRfcmYuZmVhdHVyZV9pbXBvcnRhbmNlc18sIGluZGV4PXVjaWhkX1hfdHJhaW4uY29sdW1ucykuc29ydF92YWx1ZXMoKQpheCA9IHVjaWhkX3JmX2ZlYXRfaW1wLnRhaWwoMTApLnBsb3Qoa2luZD0iYmFyaCIpCnBsdC5zaG93KCkKYGBgCgojIyMjIyBTaGFwIHZhbHVlIGZlYXR1cmUgcmFua2luZyB7LX0KCmBgYHtweXRob24gc2hhcF91Y2loZF9yZl9mZWF0X2ltcH0Kc2hhcC5zdW1tYXJ5X3Bsb3QodWNpaGRfcmZfc2hhcF92YWx1ZXMsIHVjaWhkX1hfdHJhaW4sCiAgICAgICAgICAgICAgICAgIHBsb3RfdHlwZT0iYmFyIiwgbWF4X2Rpc3BsYXk9MTAsIHNob3c9RmFsc2UpCnBsdC5zaG93KCkKYGBgCgojIyMjIExvY2FsIEV4cGxhbmF0aW9uIHstfQoKYGBge3B5dGhvbn0KdWNpaGRfcmZfc2hhcF9wbG90KHVjaWhkX3JmX3RwX2lkeFswXSkKYGBgCgpgYGB7cHl0aG9ufQp1Y2loZF9yZl9zaGFwX3Bsb3QodWNpaGRfcmZfZnBfaWR4WzBdKQpgYGAKCiMjIyBFeHBsYWluIEdyYWRpZW50IEJvb3N0aW5nIFRyZWVzCgpGb3IgR0JUIHdlIGZlZWQgdGhlIG1vZGVsIHRoYXQgaXMgb3B0aW1pemVkLAp3aGVyZSBjYXRlZ29yaWNhbHMgYXJlIGVuY29kZWQgaW50ZXJuYWxseSB3aXRob3V0IGV4cGxpY2l0IG9uZS1ob3QgZW5jb2RpbmcuCgpgYGB7cHl0aG9uIHNoYXBfdWNpaGRfbGdifQp1Y2loZF9sZ2JfZXhwbGFpbmVyID0gc2hhcC5UcmVlRXhwbGFpbmVyKHVjaWhkX2JzdF8yKQp1Y2loZF9sZ2Jfc2hhcF92YWx1ZXMgPSB1Y2loZF9sZ2JfZXhwbGFpbmVyLnNoYXBfdmFsdWVzKHVjaWhkX3Rlc3QuZHJvcCgibGFiZWwiLCBheGlzPTEpKQoKZGVmIHVjaWhkX2xnYl9zaGFwX3Bsb3QodGVzdF9pZCwgbWF0cGxvdGxpYj1UcnVlKToKICBzaGFwX3BsdCA9IHNoYXAuZm9yY2VfcGxvdCgKICAgIHVjaWhkX2xnYl9leHBsYWluZXIuZXhwZWN0ZWRfdmFsdWVbMV0sCiAgICB1Y2loZF9sZ2Jfc2hhcF92YWx1ZXNbMV1bdGVzdF9pZCw6XSwKICAgIHVjaWhkX3Rlc3QuaWxvY1tbdGVzdF9pZF1dLmRyb3AoImxhYmVsIiwgYXhpcz0xKSwKICAgIG1hdHBsb3RsaWI9bWF0cGxvdGxpYgogICkKICByZXR1cm4gc2hhcF9wbHQKYGBgCgojIyMjIEdsb2JhbCBGZWF0dXJlIEltcG9ydGFuY2Ugey19CgojIyMjIyBTcGxpdC10aW1lLWJhc2VkIGZlYXR1cmUgcmFua2luZyB7LX0KCmBgYHtweXRob24gdWNpaGRfbGdiX2ZlYXRfaW1wfQpheCA9IGxnYi5wbG90X2ltcG9ydGFuY2UodWNpaGRfYnN0XzIsIG1heF9udW1fZmVhdHVyZXM9MTApCnBsdC5zaG93KCkKYGBgCgojIyMjIyBTaGFwIHZhbHVlIGZlYXR1cmUgcmFua2luZyB7LX0KCmBgYHtweXRob24gc2hhcF91Y2loZF9sZ2JfZmVhdF9pbXB9CnNoYXAuc3VtbWFyeV9wbG90KHVjaWhkX2xnYl9zaGFwX3ZhbHVlcywgdWNpaGRfdGVzdC5kcm9wKCJsYWJlbCIsIGF4aXM9MSksCiAgICAgICAgICAgICAgICAgIHBsb3RfdHlwZT0iYmFyIiwgbWF4X2Rpc3BsYXk9MTAsIHNob3c9RmFsc2UpCnBsdC5zaG93KCkKYGBgCgojIyMjIExvY2FsIEV4cGxhbmF0aW9uIHstfQoKYGBge3B5dGhvbn0KdWNpaGRfbGdiX3NoYXBfcGxvdCh1Y2loZF9yZl90cF9pZHhbMF0pCmBgYAoKYGBge3B5dGhvbn0KdWNpaGRfbGdiX3NoYXBfcGxvdCh1Y2loZF9yZl9mcF9pZHhbMF0pCmBgYAoKIyMjIFRoZSBJbXBhY3Qgb2YgT25lLUhvdCBFbmNvZGluZyBPbiBFeHBsYW5hdGlvbgoKQXMgb25lIG1heSBub3cgcmVhbGl6ZSwKYnkgZXhwbGljaXRseSBvbmUtaG90LWVuY29kZSB0aGUgY2F0ZWdvcmljYWwgZmVhdHVyZXMgd2UgZXNzZW50aWFsbHkgc3BsaXQgdGhlbSBpbnRvIGRpZmZlcmVudCBmZWF0dXJlcyBpbiB0aGVpciBpbnRlcnByZXRhYmxlIHJlcHJlc2VudGF0aW9uLgpUaGlzIGNhbiBiZSBlaXRoZXIgZ29vZCBvciBiYWQsIGRlcGVuZGluZyBvbiB0aGUgYWN0dWFsIHVzZSBjYXNlLgpGcm9tIHRoaXMgcGFydGljdWxhciBhc3BlY3QgbGliYXJ5IHN1Y2ggYXMgYGxpZ2h0Z2JtYCBwcm92aWRlcyB0aGUgZmxleGliaWxpdHkgdG8gYWxsb3cgdXMgY2hvb3NlIHdoZXRoZXIgdG8gZG8gdGhlIG9uZS1ob3QgZW5jb2Rpbmcgb3Igbm90LgpTbyB0aGUgd2F5IHdlIHdhbnQgdG8gY29uc3RydWN0IHRoZSBleHBsYW5hdGlvbiBtb2RlbCBtYXkgd2VsbCBhZmZlY3Qgb3VyIGltcGxlbWVudGF0aW9uIG9mIHRoZSBvcmlnaW5hbCBtb2RlbCEKCiMjIE9uIEltYWdlIENsYXNzaWZpZXIKCioqVE9ETzogVXNlIGEgcHJlLXRyYWluZWQgbW9kZWw/KioKCiMgRXhwbGFpbmFibGUgQm9vc3RpbmcgTWFjaGluZQoKQG5vcmkyMDE5aW50ZXJwcmV0bWwgcHVibGlzaCB0aGUgb3BlbiBzb3VyY2UgcGFja2FnZSBgaW50ZXJwcmV0YCBmb3IgYSBmYXN0IGltcGxlbWVudGF0aW9uIG9mICoqR2VuZXJhbGl6ZWQgQWRkaXRpdmUgTW9kZWxzIHdpdGggUGFpcndpc2UgSW50ZXJhY3Rpb25zLCBvciBHQTxzdXA+Mjwvc3VwPk0qKiAoQGxvdTIwMTNhY2N1cmF0ZSkuCkFzIG9mIGByIGZvcm1hdChTeXMudGltZSgpLCAnJVktJW0tJWQnKWAsIGBpbnRlcnByZXRgIGlzIHN0aWxsIGluIGl0cyBhbHBoYSByZWxlYXNlIHdpdGggbGltaXRlZCBkb2N1bWVudGF0aW9uLgpUaGUgbGlicmFyeSBjb250YWlucyB0d28gZ3JvdXBzIG9mIG1vZGVsaW5nIGZyYW1ld29ya3M6CgorIGBnbGFzc2JveGA6IGV4cGxhbmFibGUgbWFjaGluZSBsZWFybmluZyBtb2RlbHMKKyBgYmxhY2tib3hgOiBtYWNoaW5lIGxlYXJuaW5nIGV4cGxhbmF0aW9uIG1vZGVscyAoc3VjaCBhcyBMSU1FIGFuZCBTSEFQKQoKV2UndmUgYWxyZWFkeSBjb3ZlcmVkIHRoZSBtYWluc3RyZWFtIGFwcHJvYWNoIGluIHRoZSBzZWNvbmQgZ3JvdXAsCmkuZS4sCm1vZGVscyB0aGF0IGFwcHJveGltYXRlIChsb2NhbGx5KSB0aGUgb3JpZ2luYWwgbW9kZWwgKHN1cHBvc2VkIHRvIGJlIGEgYmxhY2tib3gpIGZvciBiZXR0ZXIgZXhwbGFpbmFiaWxpdHkuClRoZSBtb3JlIGludGVyZXN0aW5nIHBhcnQgb2YgYGludGVycHJldGAgaXMgdG8gYnJpbmcgYWJvdXQgYW5vdGhlciB0eXBlIG9mIG1vZGVsIHRoYXQgaXMgcmVhZGlseSBpbnRlcnByZXRhYmxlIGZyb20gaXRzIHZlcnkgb3JpZ2luLAphbmQgeWV0IHN0aWxsIGNvbXBldGl0aXZlbHkgYWNjdXJhdGU6CioqdGhlIEV4cGxhaW5hYmxlIEJvb3N0aW5nIE1hY2hpbmUqKiwgb3IgRUJNLgoKRUJNIGlzIGFuIGFkZGl0aXZlIG1vZGVsIG9mIHRoZSBmb3JtOgoKJCQKZyhFKHkpKSA9IFxiZXRhXzAgKyBcc3VtIGZfaiAoeF9qKSArIFxzdW0gZl97aWp9KHhfaSwgeF9qKSwKJCQKCndoZXJlICRnKFxjZG90KSQgaXMgYSBsaW5rIGZ1bmN0aW9uIChzaWdtb2lkIGZvciBiaW5hcnkgY2xhc3NpZmljYXRpb24sIGZvciBhbiBleGFtcGxlKSwKJGZfaiQgaXMgdGhlICpmZWF0dXJlIGZ1bmN0aW9uKiBmb3IgdGhlICRqJC10aCBmZWF0dXJlLApsZWFybmVkIGJ5IGEgZ3JhZGllbnQgYm9vc3RpbmcgbWFjaGluZSB3aXRoIG9ubHkgdGhhdCBmZWF0dXJlIGF0IGEgdGltZSBhbmQgaW4gYSByb3VuZC1yb2JpbiBmYXNoaW9uIGZvciBhbGwgZmVhdHVyZXMuCiRmX3tpan0kIGlzIGEgKnBhaXJ3aXNlIGludGVyYWN0aW9uKiBmZWF0dXJlIGZ1bmN0aW9uIHRvIGZ1cnRoZXIgYm9vc3QgdGhlIGFjY3VyYWN5IG9mIHRoZSBtb2RlbCB3aGlsZSByZW1haW4gaW50ZXJwcmV0YWJpbGl0eS4KClRoZSBtb2RlbCBpcyBpbnRlcnByZXRhYmxlIHNpbmNlIHRoZSBjb250cmlidXRpb24gb2YgYW55IGluZGl2aWR1YWwgZmVhdHVyZSBjYW4gYmUgZGlyZWN0bHkgcXVhbnRpZmllZCBieSB0aGVpciBjb3JyZXNwb25kaW5nIGZlYXR1cmUgZnVuY3Rpb24gJGZfaiQuClN1Y2ggZXhwbGFuYXRpb24gY2FuIGV4dGVuZCB1cCB0byBwYWlyd2lzZSBpbnRlcmFjdGlvbiBpZiBwYWlyd2lzZSBmZWF0dXJlIGZ1bmN0aW9ucyBhcmUgYWxzbyBlc3RpbWF0ZWQuCgoqKlRPRE86IEhvdyB0byBkZXRlY3QgcGFpcndpc2UgaW50ZXJhY3Rpb24/IEJyaWVmIHRoZSBGQVNUIGFsZ29yaXRobS4qKgoKIyMgT24gVGV4dC9JbWFnZSBEYXRhCgpFQk0gaXMgbm90IGVmZmljaWVudCBmb3IgdGV4dCBkYXRhc2V0LgpEdWUgdG8gdGhlIGFsZ29yaXRobSdzIGRlc2lnbiBpdCB3aWxsIHJ1biB0b28gbG9uZyBmb3IgYmFnLW9mLXdvcmRzIG1vZGVsIHNpbmNlIHRoZXJlIGFyZSB0b28gbWFueSBmZWF0dXJlIGZ1bmN0aW9ucyB0byBlc3RpbWF0ZS4KSWYgd2UgZml0IGEgRUJNIHdpdGggdGhlIG1vdmllIHJldmlldyBkYXRhc2V0LApldmVuIGlmIG5vdCBhIGxhcmdlIGRhdGFzZXQsCndlIHdpbGwgZW5jb3VudGVyIE9PTSAob3V0LW9mLW1lbW9yeSkgaXNzdWUuCkFzIGEgcmVzdWx0LAp3ZSB3aWxsIHNraXAgdGhlIGRpc2N1c3Npb24gb2YgRUJNIG9uIGEgdGV4dCBjbGFzc2lmaWVyLgooVGhlIHNhbWUgcmVzdHJpY3Rpb24gYXBwbGllcyB0byBpbWFnZSBkYXRhc2V0LikKCiMjIE9uIFRhYnVsYXIgRGF0YQoKYEV4cGxhaW5hYmxlQm9vc3RpbmdDbGFzc2lmaWVyYCBoYXMgYSBgc2Npa2l0LWxlYXJuYCBmYXNoaW9uIEFQSSBhbmQgaGVuY2UgaXMgc3RyYWlnaHRmb3J3YXJkIHRvIHVzZS4KCmBgYHtweXRob24gdWNpaGRfZWJtfQpmcm9tIGludGVycHJldC5nbGFzc2JveCBpbXBvcnQgRXhwbGFpbmFibGVCb29zdGluZ0NsYXNzaWZpZXIKCnVjaWhkX2VibSA9IEV4cGxhaW5hYmxlQm9vc3RpbmdDbGFzc2lmaWVyKAogIG5fZXN0aW1hdG9ycz0xNiwgZmVhdHVyZV9uYW1lcz11Y2loZF8yLmNvbHVtbnMsIG5fam9icz0xKQpfID0gdWNpaGRfZWJtLmZpdCh1Y2loZF9YX3RyYWluLCB1Y2loZF95X3RyYWluKQoKdWNpaGRfZWJtX3loYXQgPSB1Y2loZF9lYm0ucHJlZGljdF9wcm9iYSh1Y2loZF9YX3Rlc3QpWzosMV0KdWNpaGRfZWJtX3ByZWQgPSAodWNpaGRfZWJtX3loYXQgPiAuNSkuYXN0eXBlKGludCkKCnByaW50KGNsYXNzaWZpY2F0aW9uX3JlcG9ydCh1Y2loZF95X3Rlc3QsIHVjaWhkX2VibV9wcmVkKSkKcHJpbnQocm9jX2F1Y19zY29yZSh1Y2loZF95X3Rlc3QsIHVjaWhkX2VibV95aGF0KSkKYGBgCgpUaGUgbW9kZWwgcGVyZm9ybXMgdmVyeSB3ZWxsIG9uIHRoZSBoZWFydCBkaXNlYXNlIGRhdGFzZXQsCm91dHBlcmZvcm1pbmcgYm90aCBSRiBhbmQgR0JULgoKIyMjIEdsb2JhbCBFeHBsYW5hdGlvbgoKYGludGVycHJldGAgY29tZXMgd2l0aCBhIHJpY2ggc2V0IG9mIHZpc3VhbGl6YXRpb24gdG9vbHMgKHdpdGggW2BwbG90bHlgXShodHRwczovL3Bsb3QubHkvKSBhcyBpdHMgYmFja2VuZCkuCk1vZGVsIGV4cGxhbmF0aW9uIGlzIGRpdmlkZWQgaW50byB0d28gZ3JvdXBzOgpnbG9iYWwgYW5kIGxvY2FsLgoKRm9yIGdsb2JhbCBleHBsYW5hdGlvbiwKd2UgaGF2ZSBhY2Nlc3MgdG8gYm90aCBnbG9iYWwgZmVhdHVyZSBpbXBvcnRhbmNlIGFuZCBhIHBlci1mZWF0dXJlIGZlYXR1cmUgY29udHJpYnV0aW9uIHN0YXRzLgoKYGBge3B5dGhvbiB1Y2loZF9lYm1fZ2xvYmFsX2V4cGxhaW59CnVjaWhkX2VibV9nbG9iYWwgPSB1Y2loZF9lYm0uZXhwbGFpbl9nbG9iYWwoKQojIEFsbCBmZWF0dXJlIGluZm86CnByaW50KHVjaWhkX2VibV9nbG9iYWwuc2VsZWN0b3IpCgojIEdsb2JhbCBmZWF0dXJlIGltcG9ydGFuY2UuCnVjaWhkX2VibV9nbG9iYWwudmlzdWFsaXplKCkud3JpdGVfaHRtbCgiL3RtcC91Y2loZF9lYm1fZmVhdF9pbXAuaHRtbCIsIGluY2x1ZGVfcGxvdGx5anM9RmFsc2UpCgojIEdsb2JhbCBjb250cmlidXRpb24gb24gdGhlIGZpc3J0IGZlYXR1cmUuCnVjaWhkX2VibV9nbG9iYWwudmlzdWFsaXplKDApLndyaXRlX2h0bWwoIi90bXAvdWNpaGRfZWJtX2FnZV9pbXAuaHRtbCIsIGluY2x1ZGVfcGxvdGx5anM9RmFsc2UpCgojIEdsb2JhbCBjb250cmlidXRpb24gb24gdGhlIHNlbmNvbmQgZmVhdHVyZS4KdWNpaGRfZWJtX2dsb2JhbC52aXN1YWxpemUoMSkud3JpdGVfaHRtbCgiL3RtcC91Y2loZF9lYm1fc2V4X2ltcC5odG1sIiwgaW5jbHVkZV9wbG90bHlqcz1GYWxzZSkKYGBgCgojIyMjIEZlYXR1cmUgSW1wb3J0YW5jZSB7LX0KCmBgYHtyLCBlY2hvPUZBTFNFfQpodG1sdG9vbHM6OmluY2x1ZGVIVE1MKCIvdG1wL3VjaWhkX2VibV9mZWF0X2ltcC5odG1sIikKYGBgCgojIyMjIEZlYXR1cmUgQ29udHJpYnV0aW9uOiBBZ2Ugey19CgpgYGB7ciwgZWNobz1GQUxTRX0KaHRtbHRvb2xzOjppbmNsdWRlSFRNTCgiL3RtcC91Y2loZF9lYm1fYWdlX2ltcC5odG1sIikKYGBgCgojIyMjIEZlYXR1cmUgQ29udHJpYnV0aW9uOiBHZW5kZXIgey19CgpgYGB7ciwgZWNobz1GQUxTRX0KaHRtbHRvb2xzOjppbmNsdWRlSFRNTCgiL3RtcC91Y2loZF9lYm1fc2V4X2ltcC5odG1sIikKYGBgCgojIyMgTG9jYWwgRXhwbGFuYXRpb24KCk1vcmUgaW1wb3J0YW50bHksCndlIG11c3QgYmUgYWJsZSB0byBleHBsYWluIGEgc3BlY2lmaWMgbW9kZWwgcHJlZGljdGlvbiBsb2NhbGx5LgpUaGlzIGNhbiBhbHNvIGJlIGRvbmUgZWFzaWx5IHdpdGggYSBjb3VwbGUgb2YgbGluZXM6CgpgYGB7cHl0aG9uIHVjaWhkX2VibV9sb2NhbF9leHBsYWlufQojIEV4cGxhaW4gdGhlIHNhbWUgaW5zdGFuY2VzIHByZXZpb3VzbHkgb24gUkYuCnVjaWhkX2V4cF9pbmQgPSBucC5hcnJheShbdWNpaGRfcmZfdHBfaWR4WzBdLCB1Y2loZF9yZl9mcF9pZHhbMF1dKQoKIyBXZSBjYW4gZmVlZCBtdWx0aXBsZSBleGFtcGxlcyBhdCB0aGUgc2FtZSB0aW1lLgp1Y2loZF9lYm1fbG9jYWwgPSB1Y2loZF9lYm0uZXhwbGFpbl9sb2NhbCgKICB1Y2loZF9YX3Rlc3QuaWxvY1t1Y2loZF9leHBfaW5kLDpdLCB1Y2loZF95X3Rlc3RbdWNpaGRfZXhwX2luZF0pCnVjaWhkX2VibV9sb2NhbC52aXN1YWxpemUoMCkud3JpdGVfaHRtbCgiL3RtcC91Y2loZF9lYm1fZXhwX3RwLmh0bWwiLCBpbmNsdWRlX3Bsb3RseWpzPUZhbHNlKQp1Y2loZF9lYm1fbG9jYWwudmlzdWFsaXplKDEpLndyaXRlX2h0bWwoIi90bXAvdWNpaGRfZWJtX2V4cF9mcC5odG1sIiwgaW5jbHVkZV9wbG90bHlqcz1GYWxzZSkKYGBgCgpgYGB7ciwgZWNobz1GQUxTRX0KaHRtbHRvb2xzOjppbmNsdWRlSFRNTCgiL3RtcC91Y2loZF9lYm1fZXhwX3RwLmh0bWwiKQpgYGAKCmBgYHtyLCBlY2hvPUZBTFNFfQpodG1sdG9vbHM6OmluY2x1ZGVIVE1MKCIvdG1wL3VjaWhkX2VibV9leHBfZnAuaHRtbCIpCmBgYAoKIyBSZWZlcmVuY2VzCg==